سیستم پشتیبانی تصمیم گیری فضایی وب برای وسیله مسیریابی با استفاده از نقشه های گوگل

This article presents a user-friendly web-based spatial decision support system (wSDSS) aimed at generating optimized vehicle routes for multiple vehicle routing problems that involve serving the demand located along arcs of a transportation network. The wSDSS incorporates Google Maps™ (cartography and network data), a database, a heuristic and an ant-colony meta-heuristic developed by the authors to generate routes and detailed individual vehicle route maps. It accommodates realistic system specifics, such as vehicle capacity and shift time constraints, as well as network constraints such as one-way streets and prohibited turns. The wSDSS can be used for “what-if” analysis related to possible changes to input parameters such as vehicle capacity, maximum driving shift time, seasonal variations of demand, network modifications, and imposed arc orientations. Since just a web browser is needed, it can be easily adapted to be widely used in many real-world situations. The system was tested for urban trash collection in Coimbra, Portugal.

1.1. The importance and impacts of vehicle routing problems The transportation of goods and services imposes considerable costs on both the public and private sectors of the economy as well as the environment. More efficient vehicle routing can improve a firm's competitive advantage, increase the efficiency of supplying public services, and reduce energy consumption, traffic congestion and air pollution, which are growing problems in many urban areas. Vehicle travel increased substantially in recent decades. Total vehicle miles of travel (VMT) in the United States increased 63% between 1980 and 1997 and it has more than doubled between 1970 and 2000. The rate of growth in VMT has exceeded significantly the rate of population growth, employment growth, and economic growth over the last decade of the 20th century [7]. In China total motorized passenger-km rose sixfold between 1980 and 2003, and freight distance increased nearly fivefold in that period [30]. In cities, the movement of goods may account for 20 to 30% of the total vehicle miles traveled, and for 16 to 50% of all air pollutants resulting from transportation [6]. Urban freight transportation is on one hand an important economic activity but on the other hand is rather disturbing (traffic congestion, noise and other environmental impacts). Issues related to freight transportation are pertinent in an urban context (where the number of vehicles, congestion and pollution levels are increasing fast) and therefore they need to be well understood and quantified. In what concerns environmental impacts, some recent studies emphasize the optimization of route choice based on the lowest total fuel consumption and thus the emission of CO2[8]. However, many see the need for a threefold strategic approach: improving fuel economy, decreasing VMT and lowering the carbon content of fuels. Woodcock et al. [30] also refer to several main strategies jointly required for moving to low-carbon transport, being shortening trip distances one of them. Similar findings are also supported by other authors (e.g., [27]) stating that currently there are no cost-effective technological solution available for mass deployment to reduce CO2 emissions, so the only way is to increase the use of alternative fuels, greater efficiency in fuel use, increased occupancy and load factors, and through reducing the distances travelled. This research may be included in this global strategy, as a contribution for reducing miles traveled in vehicle routing problems in an urban setting. In what concerns transportation and injuries, Woodcock et al. [30] mentioned that, because of the growth in traffic, many people are exposed to levels of kinetic energy that can result in serious injury, being estimated that in 2002 1.2 million people were killed and 50 million people were injured in road-traffic crashes, and these figures continue to rise. Moreover, heavy goods vehicles are twice as likely to be involved in fatal crashes than are cars, per kilometer travelled. Therefore, reducing VMT is also an important issue in what concerns these types of risks imposed on people's health. Dablanc [6] calls for improved logistics in European cities. Improved logistics also would benefit the United States of America where freight transportation costs account for approximately 6% of the gross domestic product (GDP) [15]. The importance of transportation problems has been acknowledged by the scientific community. However, the optimization of transportation routing is computationally intractable for most real-world problems (e.g., [9] and [16]). This has justified the development of heuristic approaches to generate (optimal or near-optimal) solutions in acceptable computer times. As a consequence, the design and implementation of exact and heuristic solution algorithms for such problems constitute an interesting challenge for operations research (OR) and transportation science, both from a methodological perspective and practical decision support purposes to address all the issues mentioned above. The potential benefits of OR models and methods applied to transportation systems, having in mind the implementation in practice, has constituted a research avenue followed by the authors, namely concerning the development of strategies to deal with real-world urban vehicle collection/delivery problems [4] and [23] and new approaches for routing problems [22], [24] and [25]. These methodological innovations were conveniently adapted and incorporated in the implementation of the web-based spatial decision support system (wSDSS) presented in this paper. 1.2. DSS and ICT in transportation problems Due to the data requirements and the complexity of urban planning and transportation problems, there has been a growing interest in the use of decision support systems (DSS) to analyze them at the operational (e.g., [17] and [26]), the tactical (e.g., [18]) and the strategic planning levels (e.g., [5] and [29]). Adequate graphical interfaces are important to represent solutions in routing problems given their strong spatial component. Information and communication technologies (ICT) can play an important role for constructing tools embedding algorithms, graphical interfaces and access to remote data through the Internet. Due to the spatial nature of these problems, geographical information systems (GIS) have been a natural component of such DSS as they are important tools for collecting, organizing, and displaying spatial data in a large variety of planning applications, such as in vehicle routing problems [20] and [23]. Hans [11] enhanced the importance of the development of GIS for urban transportation planning and modeling, including network-based urban transportation planning, and the incorporation of network data into a GIS framework in order to have a high-speed interactive system suitable for providing near real-time alternatives and policy analysis. Although transportation research has been “late to embrace GIS as a key technology to support its research and operational needs” [28], there has been an increase of such research in recent years. Much of this research also incorporates exact and heuristic solution algorithms with the GIS (e.g., [1], [5], [12], [17], [19], [23] and [26]). The development of decision support tools profiting from state-of-the-art ICT is an important avenue of research. World Wide Web technologies have transformed the design, development, implementation and deployment of DSS; however, it is recognized that the use of Web-based computation to deploy DSS applications for remote access remains less common [3]. In the field of transportation, some recent developments can be found, e.g., Ray [21] has developed a web-based spatial DSS for managing the movement of oversize and overweight vehicles over highways. The importance of ICT, besides GIS technology, is acknowledged in several fields related to transportation [2] and [14]. In what concerns transportation problems, the Internet enables the implementation of web-based GIS systems, allowing users to interact with networks, maps, and GIS tools through a browser (e.g., [20]). The Internet potentiates new approaches due to two principal reasons: the advanced capabilities offered, unique amongst other ICTs, and because of its widespread adoption [13]. On the other hand, the availability and price of adequate up-to-date cartography has been a drawback in GIS-based systems. Furthermore, a network structure (defined on maps) is required to be used as input data and also for running the routing optimization algorithms. Google Maps™ services may overcome those limitations by providing access, through the Internet, to cartography and to road/street network structures, as well as to important real data associated with roads and traffic restrictions (e.g., one-way streets, prohibited left and U-turns). In addition, it supplies travel times for each street or road based on the respective speed limits. Thus, exploring this particular ICT capabilities provided by the Internet coupled with Google Maps™ services is a promising avenue for developing web-based spatial DSS incorporating specific algorithms for routing optimization problems. 1.3. The aim of this research In this article, we present a wSDSS integrating optimization methodologies (e.g., heuristics and ant-colony meta-heuristics) previously developed, improved and tested by the authors, designed for multiple vehicle routing problems [23], [24] and [25]. These methodologies were adapted in order to satisfy several additional constraints of actual problems (as explained in the next section) before their integration into the system. The wSDSS was tested on a real-world multiple vehicle routing problem: trash collection in the City of Coimbra, Portugal. Although the application presented in this paper is a specific one, the wSDSS is applicable to several public and private sector vehicle routing problems. The system can be used for short-term analysis (e.g., the design of daily vehicle routes) and long-term analysis (e.g., deciding how many vehicles to operate in a fleet). Several important design criteria for the wSDSS were defined. First, it must generate efficient vehicle collection routes quickly as demand patterns and routes can change seasonally or even daily. Second, the system must be intuitive enough to be used by people with little or no background in OR models and methods. Third, the wSDSS must generate individual route maps and directions for the drivers. Fourth, the system must be able to incorporate various operational and local network specific conditions and constraints. Fifth, it is also desirable for the system to be able to analyze long-term decisions, such as the number (and/or size) of vehicles to operate and the length of an employee's work shift. Finally, the system must be “universal” (virtually usable at any place on Earth), using public access cartography and real road network data through the Internet (Google Maps™) via a standard browser (i.e., not requiring the installation of special client software). The remainder of this article is organized as follows. A brief description of the main characteristics of the routing problem is made in Section 2. The architecture of the wSDSS including some implementation details is presented in Section 3. Some illustrative results are presented and discussed in Section 4. A summary and conclusions are provided in the last section.

A web-based decision support system (wDSS) prototype using GoogleMaps™ and incorporating state-of-the-art heuristics and meta-heuristic approaches developed by the authors was presented. The wDSS was designed to be entirely accessed via an Internet browser. Several features make the system an innovative coupling of sound algorithmic approaches with modern information and communication technologies: 1.It extends a well-known routing problem (the CARP) by incorporating realistic system specifics (such as shift time constraints, the possibility of considering the “drop-off point” not at the same location as the depot where the vehicles start and end their shifts), and network constraints such as one-way streets and prohibited turns. 2.It requires only an Internet browser to be used that allows remote access to cartography, networks data, and algorithms via the web. 3.It uses state-of-the-art methodologies for routing problems previously developed by the authors [4], [24] and [25], which were adapted to accommodate additional conditions/constraints of real-world routing problems. 4.It accesses maps and streets network data provided by Google Maps™ services and represents solutions (routes) graphically on Google Maps™ cartography with lists of directions and the sequence of streets as they are traveled by the vehicle, displaying accumulated length, load, and time for the route as it progresses from arc to arc. Although the SDSS was tested for an urban trash collection situation, which is an important actual problem in modern cities, it can be adapted to be used in other real-world problems of capacitated routing (e.g., street sweeping, snow cleaning vehicles, door-to-door collection/delivery of goods, and inspection of streets or other infrastructures).