Determining time-dependent minimum cost paths under several objectives

doi:10.1016/j.cor.2019.01.007

Return

Determining time-dependent minimum cost paths under several objectives

2019-05-01

PRE

Hamza Heni *

Leandro C. Coelho

Jacques Renaud

DOI：10.1016/j.cor.2019.01.007

Original

Original request for help

Save

Abstract

En 中文

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. (C) 2019 Elsevier Ltd. All rights reserved.

Keywords:

Time-dependent networks

Congestion

Emission

Quickest path

Bounds

Label-setting algorithm

Link travel time

Flow speed model

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.