×

Determining time-dependent minimum cost paths under several objectives. (English) Zbl 1458.90100

Summary: As the largest contributor to greenhouse gas (GHG) emissions in the transportation sector, road freight transportation is the focus of numerous strategies to tackle increased pollution. One way to reduce emissions is to consider congestion and being able to route traffic around it. In this paper, we study time-dependent minimum cost paths under several objectives (TDMCP-SO), in which the objective function comprises GHG emissions, driver and congestion costs. Travel costs are impacted by traffic due to changing congestion levels depending on the time of the day, vehicle types and carried load. We also develop time-dependent lower and upper bounds, which are both accurate and fast to compute. Computational experiments are performed on real-life instances that incorporate the variation of traffic throughout the day, by adapting Dijkstra’s label-setting algorithm according to different cost computation methods. We show that explicitly considering first-in, first-out (FIFO) consistency using time-varying speeds allows the efficient computation of tight time-dependent bounds. Our computational results demonstrate that the TDMCP-SO is more difficult to solve to optimality but the proposed algorithm is shown to be robust and efficient in reducing the total cost even for large instances in an environment of varying speeds, outperforming those based on the link travel time model and on the smoothing method according to each optimization objective, flexible departure times, and different load patterns.

MSC:

90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Barth, M.; Boriboonsomsin, K., Real-world carbon dioxide impacts of traffic congestion, Transp. Res. Rec., 2058, 163-171 (2008)
[2] Barth, M.; Boriboonsomsin, K., Energy and emissions impacts of a freeway-based dynamic eco-driving system, Transp. Res. Part D, 14, 6, 400-410 (2009)
[3] Bektaş, T.; Laporte, G., The pollution-routing problem, Transp. Res. Part B, 45, 8, 1232-1250 (2011)
[4] Belhassine, K.; Coelho, L. C.; Renaud, J.; Gagliardi, J.-P., Improved Home Deliveries in Congested Areas Using Geospatial Technology, Technical Report CIRRELT-2018-02 (2018)
[5] Brodal, G. S.; Jacob, R., Time-dependent networks as models to achieve fast exact time-table queries, Electron. Notes Theor. Comput. Sci., 92, 3-15 (2004) · Zbl 1271.90020
[6] Calogiuri, T.; Ghiani, G.; Guerriero, E., The time-dependent quickest path problem: properties and bounds, Networks, 66, 2, 112-117 (2015) · Zbl 1390.90057
[7] Cooke, K. L.; Halsey, E., The shortest route through a network with time-dependent internodal transit times, J. Math. Anal. Appl., 14, 3, 493-498 (1966) · Zbl 0173.47601
[8] Dabia, S.; Demir, E.; Van Woensel, T., An exact approach for a variant of the pollution-routing problem, Transp. Sci., 51, 2, 607-628 (2017)
[9] Dean, B. C., Algorithms for minimum-cost paths in time-dependent networks with waiting policies, Networks, 44, 1, 41-46 (2004) · Zbl 1103.90025
[10] Dean, B. C., Shortest Paths in FIFO Time-Dependent Networks: Theory and Algorithms, Technical Report (2004), Massachusetts Institute of Technology
[11] Dehne, F.; Omran, M. T.; Sack, J.-R., Shortest paths in time-dependent FIFO networks, Algorithmica, 62, 1-2, 416-435 (2012) · Zbl 1241.68088
[12] Delling, D.; Nannicini, G., Core routing on dynamic time-dependent road networks, INFORMS J. Comput., 24, 2, 187-201 (2012) · Zbl 1460.90054
[13] Demir, E.; Bektaş, T.; Laporte, G., An adaptive large neighborhood search heuristic for the pollution-routing problem, Eur. J. Oper. Res., 223, 2, 346-359 (2012) · Zbl 1292.90045
[14] Demir, E.; Bektaş, T.; Laporte, G., The bi-objective pollution-routing problem, Eur. J. Oper. Res., 232, 3, 464-478 (2014) · Zbl 1305.90053
[15] Demir, E.; Bektaş, T.; Laporte, G., A review of recent research on green road freight transportation, Eur. J. Oper. Res., 237, 3, 775-793 (2014) · Zbl 1338.90004
[16] Di Bartolomeo, M.; Grande, E.; Nicosia, G.; Pacifici, A., Cheapest paths in dynamic networks, Networks, 55, 2, 23-32 (2017) · Zbl 1390.90155
[17] Ehmke, J. F.; Campbell, A. M.; Thomas, B. W., Data-driven approaches for emissions-minimized paths in urban areas, Comput. Oper. Res., 67, 34-47 (2016) · Zbl 1349.90084
[18] Ehmke, J. F.; Campbell, A. M.; Thomas, B. W., Vehicle routing to minimize time-dependent emissions in urban areas, Eur. J. Oper. Res., 251, 2, 478-494 (2016) · Zbl 1346.90102
[19] Ehmke, J. F.; Campbell, A. M.; Thomas, B. W., Optimizing for total costs in vehicle routing in urban areas, Transp. Res. Part E, 116, 242-265 (2018)
[20] Ehmke, J. F.; Meisel, S.; Mattfeld, D. C., Floating car based travel times for city logistics, Transp. Res. Part C, 21, 1, 338-352 (2012)
[21] Fleischmann, B.; Gietz, M.; Gnutzmann, S., Time-varying travel times in vehicle routing, Transp. Sci., 38, 2, 160-173 (2004)
[22] Franceschetti, A.; Demir, E.; Honhon, D.; Van Woensel, T.; Laporte, G.; Stobbe, M., A metaheuristic for the time-dependent pollution-routing problem, Eur. J. Oper. Res., 259, 3, 972-991 (2017) · Zbl 1402.90017
[23] Franceschetti, A.; Honhon, D.; Van Woensel, T.; Bektaş, T.; Laporte, G., The time-dependent pollution-routing problem, Transp. Res. Part B, 56, 265-293 (2013)
[24] Gao, S.; Chabini, I., Optimal routing policy problems in stochastic time-dependent networks, Transp. Res. Part B, 40, 2, 93-122 (2006)
[25] Gao, S.; Huang, H., Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks, Transp. Res. Part C, 21, 1, 196-213 (2012)
[26] Ghiani, G.; Guerriero, E., A lower bound for the quickest path problem, Comput. Oper. Res., 50, 154-160 (2014) · Zbl 1348.90594
[27] Hart, P. E.; Nilsson, N. J.; Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cyber., 4, 2, 100-107 (1968)
[28] Hickman, J., Hassel, D., Joumard, R., Samaras, Z., Sorenson, S., 1999. Methodology for calculating transport emissions and energy consumption. URL: http://www.transport-research.info/sites/default/files/project/documents/meet.pdf; Hickman, J., Hassel, D., Joumard, R., Samaras, Z., Sorenson, S., 1999. Methodology for calculating transport emissions and energy consumption. URL: http://www.transport-research.info/sites/default/files/project/documents/meet.pdf
[29] Huang, H.; Gao, S., Optimal paths in dynamic networks with dependent random link travel times, Transp. Res. Part B, 46, 5, 579-598 (2012)
[30] Huang, Y.; Zhao, L.; Van Woensel, T.; Gross, J.-P., Time-dependent vehicle routing problem with path flexibility, Transp. Res. Part B, 95, 169-195 (2017)
[31] Ichoua, S.; Gendreau, M.; Potvin, J. Y., Vehicle dispatching with time-dependent travel times, Eur. J. Oper. Res., 144, 2, 379-396 (2003) · Zbl 1012.90003
[32] Jabali, O.; Van Woensel, T.; de Kok, A.-G., Analysis of travel times and \(CO_2\) emissions in time-dependent vehicle routing, Prod. Oper. Manag., 21, 6, 1060-1074 (2012)
[33] Kok, A. L.; Hans, E.; Schutten, J., Vehicle routing under time-dependent travel times: the impact of congestion avoidance, Comput. Oper. Res., 39, 5, 910-918 (2012) · Zbl 1251.90021
[34] Miller-Hooks, E.; Yang, B., Updating paths in time-varying networks given arc weight changes, Transp. Sci., 39, 4, 451-464 (2005)
[35] Ministère de l’Énergie et des Ressources Naturelles, 2014. Facteurs d’émission et de conversion. Bureau de l’Efficacité et de l’Innovation Énergétique, Gouvernement du Québec. URL: http://www.transitionenergetique.gouv.qc.ca/fileadmin/medias/pdf/Facteurs_emissions.pdf; Ministère de l’Énergie et des Ressources Naturelles, 2014. Facteurs d’émission et de conversion. Bureau de l’Efficacité et de l’Innovation Énergétique, Gouvernement du Québec. URL: http://www.transitionenergetique.gouv.qc.ca/fileadmin/medias/pdf/Facteurs_emissions.pdf
[36] Orda, A.; Rom, R., Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length, J. Assoc. Comput. Mach., 37, 3, 607-625 (1990) · Zbl 0699.68074
[37] Qian, J.; Eglese, R., Fuel emissions optimization in vehicle routing problems with time-varying speeds, Eur. J. Oper. Res., 248, 3, 840-848 (2016) · Zbl 1346.90167
[38] Savelsbergh, M.; Van Woensel, T., City logistics: challenges and opportunities, Transp. Sci., 50, 2, 579-590 (2016)
[39] Sherali, H. D.; Hobeika, A. G.; Kangwalklai, S., Time-dependent, label-constrained shortest path problems with applications, Transp. Sci., 37, 3, 278-293 (2003)
[40] Sun, Y.; Yu, X.; Bie, R.; Song, H., Discovering time-dependent shortest path on traffic graph for drivers towards green driving, J. Netw. Comput. Appl., 83, 204-212 (2017)
[41] Sung, K.; Bell, M. G.; Seong, M.; Park, S., Shortest paths in a network with time-dependent flow speeds, Eur. J. Oper. Res., 121, 1, 32-39 (2000) · Zbl 0959.90009
[42] Transports Canada, 2017. Transportation in Canada 2016. URL: https://www.tc.gc.ca/media/documents/policy/comprehensive_report_2016.pdf; Transports Canada, 2017. Transportation in Canada 2016. URL: https://www.tc.gc.ca/media/documents/policy/comprehensive_report_2016.pdf
[43] Turkensteen, M., The accuracy of carbon emission and fuel consumption computations in green vehicle routing, Eur. J. Oper. Res., 262, 2, 647-659 (2017) · Zbl 1375.90059
[44] Van Woensel, T.; Kerbache, L.; Peremans, H.; Vandaele, N., Vehicle routing with dynamic travel times: a queueing approach, Eur. J. Oper. Res., 186, 3, 990-1007 (2008) · Zbl 1146.90426
[45] Wen, L.; Çatay, B.; Eglese, R., Finding a minimum cost path between a pair of nodes in a time-varying road network with a congestion charge, Eur. J. Oper. Res., 236, 3, 915-923 (2014) · Zbl 1304.90047
[46] Wen, L.; Eglese, R., Minimum cost VRP with time-dependent speed data and congestion charge, Comput. Oper. Res., 56, 41-50 (2015) · Zbl 1348.90140
[47] Yang, L.; Zhou, X., Constraint reformulation and a lagrangian relaxation-based solution algorithm for a least expected time path problem, Transp. Res. Part B, 59, 22-44 (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.