Site Loader
Rock Street, San Francisco

This article presents a user-friendly web-based spatial decision support system (wSDSS) aimed at generatingoptimized vehicle routes for multiple vehicle routing problems that involve serving the demand located alongarcs of a transportation network. The wSDSS incorporates Google Maps™ (cartography and network data), adatabase, a heuristic and an ant-colony meta-heuristic developed by the authors to generate routes anddetailed individual vehicle route maps. It accommodates realistic system specifics, such as vehicle capacityand shift time constraints, as well as network constraints such as one-way streets and prohibited turns. ThewSDSS can be used for “what-if” analysis related to possible changes to input parameters such as vehiclecapacity, maximum driving shift time, seasonal variations of demand, network modifications, and imposedarc orientations. Since just a web browser is needed, it can be easily adapted to be widely used in many realworldsituations. The system was tested for urban trash collection in Coimbra, Portugal.The transportation of goods and services imposes considerablecosts on both the public and private sectors of the economy as well asthe environment. More efficient vehicle routing can improve a firm’scompetitive advantage, increase the efficiency of supplying publicservices, and reduce energy consumption, traffic congestion and airpollution, which are growing problems in many urban areas. Vehicletravel increased substantially in recent decades. Total vehicle miles oftravel (VMT) in the United States increased 63% between 1980 and1997 and it has more than doubled between 1970 and 2000. The rateof growth in VMT has exceeded significantly the rate of populationgrowth, employment growth, and economic growth over the lastdecade of the 20th century 7. In China total motorized passenger-kmrose sixfold between 1980 and 2003, and freight distance increasednearly fivefold in that period 30. In cities, the movement of goodsmay account for 20 to 30% of the total vehicle miles traveled, andfor 16 to 50% of all air pollutants resulting from transportation6. Urban freight transportation is on one hand an importanteconomic activity but on the other hand is rather disturbing (trafficcongestion, noise and other environmental impacts). Issues relatedto freight transportation are pertinent in an urban context (wherethe number of vehicles, congestion and pollution levels are increasingfast) and therefore they need to be well understood andquantified.In what concerns environmental impacts, some recent studiesemphasize the optimization of route choice based on the lowesttotal fuel consumption and thus the emission of CO2 8. However,many see the need for a threefold strategic approach: improvingfuel economy, decreasing VMT and lowering the carbon content offuels. Woodcock et al. 30 also refer to several main strategiesjointly required for moving to low-carbon transport, being shorteningtrip distances one of them. Similar findings are also supportedby other authors (e.g., 27) stating that currently there are no costeffectivetechnological solution available for mass deployment toreduce CO2 emissions, so the only way is to increase the use ofalternative fuels, greater efficiency in fuel use, increased occupancyand load factors, and through reducing the distances travelled. Thisresearch may be included in this global strategy, as a contributionfor reducing miles traveled in vehicle routing problems in an urbansetting.In what concerns transportation and injuries, Woodcock et al. 30mentioned that, because of the growth in traffic, many people areexposed to levels of kinetic energy that can result in serious injury,being estimated that in 2002 1.2 million people were killed and50 million people were injured in road-traffic crashes, and thesefigures continue to rise. Moreover, heavy goods vehicles are twice aslikely to be involved in fatal crashes than are cars, per kilometertravelled. Therefore, reducing VMT is also an important issue in whatconcerns 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 Americawhere freight transportation costs account for approximately 6% ofthe gross domestic product (GDP) 15.The importance of transportation problems has been acknowledgedby the scientific community. However, the optimization oftransportation routing is computationally intractable for most realworldproblems (e.g., 9,16). This has justified the development ofheuristic approaches to generate (optimal or near-optimal) solutionsin acceptable computer times. As a consequence, the design andimplementation of exact and heuristic solution algorithms forsuch problems constitute an interesting challenge for operationsresearch (OR) and transportation science, both from a methodologicalperspective and practical decision support purposes toaddress all the issues mentioned above. The potential benefits ofOR models and methods applied to transportation systems, havingin mind the implementation in practice, has constituted a researchavenue followed by the authors, namely concerning the developmentof strategies to deal with real-world urban vehicle collection/delivery problems 4,23 and new approaches for routing problems22,24,25. These methodological innovations were convenientlyadapted and incorporated in the implementation of theweb-based spatial decision support system (wSDSS) presented inthis paper.1.2. DSS and ICT in transportation problemsDue to the data requirements and the complexity of urbanplanning and transportation problems, there has been a growinginterest in the use of decision support systems (DSS) to analyze themat the operational (e.g., 17,26), the tactical (e.g., 18) and thestrategic planning levels (e.g., 5,29). Adequate graphical interfacesare important to represent solutions in routing problems given theirstrong spatial component. Information and communication technologies(ICT) can play an important role for constructing toolsembedding algorithms, graphical interfaces and access to remote datathrough the Internet. Due to the spatial nature of these problems,geographical information systems (GIS) have been a natural componentof such DSS as they are important tools for collecting, organizing,and displaying spatial data in a large variety of planningapplications, such as in vehicle routing problems 20,23. Hans11 enhanced the importance of the development of GIS forurban transportation planning and modeling, including networkbasedurban transportation planning, and the incorporation ofnetwork data into a GIS framework in order to have a high-speedinteractive system suitable for providing near real-time alternativesand policy analysis. Although transportation researchhas been “late to embrace GIS as a key technology to support itsresearch and operational needs” 28, there has been an increaseof such research in recent years. Much of this research alsoincorporates exact and heuristic solution algorithms with the GIS(e.g., 1,5,12,17,19,23,26).The development of decision support tools profiting from state-ofthe-art ICT is an important avenue of research. World Wide Webtechnologies have transformed the design, development, implementationand deployment of DSS; however, it is recognized that the useof Web-based computation to deploy DSS applications for remoteaccess remains less common 3. In the field of transportation, somerecent developments can be found, e.g., Ray 21 has developed a webbasedspatial DSS for managing the movement of oversize andoverweight vehicles over highways.The importance of ICT, besides GIS technology, is acknowledged inseveral fields related to transportation 2,14. In what concernstransportation problems, the Internet enables the implementation ofweb-basedGIS systems, allowing users to interactwith networks,maps,and GIS tools through a browser (e.g., 20). The Internet potentiatesnewapproaches due to two principal reasons: the advanced capabilitiesoffered, unique amongst other ICTs, and because of its widespreadadoption 13.On the other hand, the availability and price of adequate up-todatecartography has been a drawback in GIS-based systems.Furthermore, a network structure (defined on maps) is required tobe used as input data and also for running the routing optimizationalgorithms. Google Maps™ services may overcome those limitationsby providing access, through the Internet, to cartography and to road/street network structures, as well as to important real data associatedwith roads and traffic restrictions (e.g., one-way streets, prohibitedleft and U-turns). In addition, it supplies travel times for each street orroad based on the respective speed limits. Thus, exploring thisparticular ICT capabilities provided by the Internet coupled withGoogle Maps™ services is a promising avenue for developing webbasedspatial DSS incorporating specific algorithms for routingoptimization problems.1.3. The aim of this researchIn this article, we present a wSDSS integrating optimizationmethodologies (e.g., heuristics and ant-colony meta-heuristics)previously developed, improved and tested by the authors,designed for multiple vehicle routing problems 23–25. Thesemethodologies were adapted in order to satisfy several additionalconstraints of actual problems (as explained in the next section)before their integration into the system. The wSDSS was tested on areal-world multiple vehicle routing problem: trash collection in theCity of Coimbra, Portugal. Although the application presented in thispaper is a specific one, the wSDSS is applicable to several public andprivate sector vehicle routing problems. The system can be used forshort-term analysis (e.g., the design of daily vehicle routes) andlong-term analysis (e.g., deciding how many vehicles to operate in afleet).Several important design criteria for the wSDSS were defined.First, it must generate efficient vehicle collection routes quickly asdemand patterns and routes can change seasonally or even daily.Second, the system must be intuitive enough to be used by peoplewith little or no background in OR models and methods. Third, thewSDSS must generate individual route maps and directions for thedrivers. Fourth, the system must be able to incorporate variousoperational and local network specific conditions and constraints.Fifth, it is also desirable for the system to be able to analyze long-termdecisions, such as the number (and/or size) of vehicles to operate andthe length of an employee’s work shift. Finally, the system must be”universal” (virtually usable at any place on Earth), using publicaccess cartography and real road network data through the Internet(Google Maps™) via a standard browser (i.e., not requiring theinstallation of special client software).The remainder of this article is organized as follows. A briefdescription of the main characteristics of the routing problem is madein Section 2. The architecture of the wSDSS including someimplementation details is presented in Section 3. Some illustrativeresults are presented and discussed in Section 4. A summary and conclusions are provided in the last section.2. Background: The underlying routing problemVehicle routing is a common and costly problem faced by manyprivate and public sector companies, with important economic, socialand environmental aspects, as described in the Introduction. Basically,the wSDSS implemented addresses arc routing problems withapplications in many real-world situations. Examples include thecollection/distribution of goods along streets, street cleaning, water,gas, and electricity meter reading, pipe or road inspection, maildelivery, and the collection of urban solid waste 4. Many of theseapplications can be structured as a capacitated arc routing problem(CARP), introduced by Golden and Wong 10. In this problemdemand occurs along the arcs, some arcs in the network may notrequire service (i.e., have no demand along them) and the vehicleshave a capacity on the total demand that they can serve. Goldenand Wong 10 proved that CARP belongs to the class of NP-hardproblems.The authors have recently addressed the CARP by developinga new improved path-scanning heuristic 24, and an ant-colonymeta-heuristic approach 25. Nevertheless, they have also recognizedin previous research works that a real-world arc routingproblem (e.g., an urban trash collection problem) cannot be approachedexactly as a CARP because of various specific operationalconditions/constraints that complicate the vehicle routing problem4,23. Therefore, the algorithms implemented to deal with theformal CARP had to be adapted and extended to accommodatemore requirements of the real-world problems. We refer to such arouting problem as the constrained CARP or C-CARP. These specificoperational conditions/constraints that differentiate C-CARP fromCARP include:1. One-way streets (i.e., the network includes directed arcs);2. Prohibited turns (e.g., U-turns and left turns) at some networkintersections;3. The route “drop-off point” (i.e., the landfill in this case), which isnot at the same location as the depot where the vehicles start andend their shifts;4. Vehicles that can serve more than one route in a day (All routes fora particular vehicle must include a “drop-off point” – a land fill inthis case. Only the last route for each vehicle must return to thestarting depot immediately after visiting the “drop-off point.”);5. The maximum shift duration for all vehicles in a day, whichrepresents the maximum hours that the vehicle’s crew can workthat day.The algorithms previously developed and validated for CARP weretaken as good starting tools for implementing a wSDSS dedicated torouting problems. The description of the particularities of thoseunderlying approaches is beyond the scope of this paper – the readeris referred to Santos et al. 24,25 for a more formal and detaileddescription of the particular heuristic and meta-heuristic approachesthat were adopted to be included in the solver engine at the core ofthe wSDSS. However, to develop a solution procedure for C-CARP(considering all the conditions/constraints enumerated above), thoseheuristic and meta-heuristic approaches needed to be adaptedconveniently.Other general requirements, not directly related to routingproblems, were taken into consideration in the design of the wSDSS,such as the remote access to digital maps and network data, as well asproducing a web application only requiring an Internet browser. Inwhat concerns the requirements related to the human–computergraphical interface, access to cartography and network data, GoogleMaps™ appeared to be the best tool due to its universal availabilityvia the web and inherent possibilities of accessing remotely roadnetwork data and constraints. This has been perceived as an effectiveway of merging together the distinct vehicle routing methodologiesdeveloped by the authors mentioned above (after a convenientadaptation to the conditions/constraints of the C-CARP), by couplingthem with Google Maps™ in order to obtain a functional (and easyto-use) prototype system able to be used by decision makers in realproblems. This way, the use of ICT turned possible that soundmethodologies could be used in practice for important routingproblems by linking them together, providing an adequate userinterfaceto support spatial representations of the problems, andenabling the remote access to urban data through the Internet forfeeding the algorithms.3. Architecture of the wSDSS3.1. Implementation detailsThe design criteria for the wSDSS were stated above. Input andoutput requirements were defined as well as the desired analytical/planning capabilities. These include the ability to generate solutionswith algorithmic approaches embedded in the system (which are”transparent” for the user), generate maps and instructions for individualvehicle routes and system solutions, produce detailed tabular informationabout routes, and represent solutions using an Internet browser.To achieve these objectives, the wSDSS requires raw data, datainformation management and analysis capabilities, and graphicaldisplay capabilities. Given these requirements and the spatial natureof the data, a system using Google Maps™ services was considered tobe the most appropriate. Consequently, the wSDSS was implementedincorporating state-of-the-art optimization algorithms (heuristic andmeta-heuristic approaches as mentioned in Section 2), and accessingGoogle Maps™ cartography and street networks data via the Internet.The data for each problem are stored in a database also accessible viathe Internet. The schematic representation of the architecture andmodus operandi of the implemented system is presented in Fig. 1. TheASP.Net web application framework, and the C# and JavaScriptprogramming languages were used in the development of the system.The database was developed using the Microsoft SQL Server Express.The user accesses the wSDSS (the data of each problem and thealgorithms operating on them) via an Internet browser.The wSDSS was tested in the City of Coimbra (an old Portuguesecity of about 120 000 inhabitants, with an historical center). As usualin old cities, an important central core zone exists in Coimbra wherethe road network is dense and characterized by a broad variety ofstreets in terms of width and number of lanes, with very narrow andone-way streets, high traffic, and endemic congestion problems. Thaturban core area of Coimbra, including its historical center, with thehighest demand per area and the most complex routing options, hasbeen selected as a challenging test field for the trash collectionproblems tackled using the wSDSS.3.2. wSDSS interfaceThe interface is supported by a standard web browser windowwhere the map of Google Maps™ occupies the central area. A bar withdrop-down menus is displayed on the top of the map area offeringfour main menus: “Edit Networks,” “Shortest Paths,” “Solve Problem”and “Show Results.” A left-hand sidebar exists where editable fields tobe filled in become available for inputting data and buttons appear,consistently with the options selected in the main menus (asdescribed in Section 3.3). A right-hand sidebar supports lists withthe representation of results available after solving a problem (asdescribed in Section 3.4).3.3. wSDSS inputAmong other features, the system includes different menus thatprovide several possibilities of input data edition. Problem parameterseither related to arcs (such as arc traversal times and service demand)

Post Author: admin


I'm Glenda!

Would you like to get a custom essay? How about receiving a customized one?

Check it out