vehicle routing; time-dependent travel times; heuristics; case study
Abstract :
[en] A substantial increase in transport intensity for passenger and freight traffic has been observed during the last decades and research confirms that this trend will continue in the years to come. Economic centres have turned into heavily congested areas. The freight transport sector incurs excessive waiting times on the road as well as at intermediate stops (e.g. sea terminals, loading or unloading points). This may cause economic losses and environmental damages. Waiting times may be avoided by taking into account congestion in freight transport planning. Vehicle routing problems arise when several pickup and delivery operations need to be performed, mainly by truck, over relatively short distances [1]. Congestion leads to uncertain travel times on links and uncertain waiting times at pickup or delivery locations. Peak hours may be avoided on congested road segments by changing the order in which customers are served. On the other hand, time slots at customer sites may be renegotiated, creating more flexibility to avoid congestion on the road and at customer stops. The objective of this paper is to estimate the benefits of taking congestion into account in transport planning and to quantify the impact of delivery restrictions on transport costs.
A highly congested road network raises the need for robust vehicle routing decisions. Current traffic conditions give rise to uncertain travel times. The reliability of travel time on a route is one of the dominant factors affecting route and departure time choices in passenger transport [2]. Similarly, in freight transport the reliability of travel times may be taken into account when planning vehicle routes. In this paper congestion is modelled as time-dependent travel times. These travel times take into account the dynamics of the time lost due to congestion using the Bureau of Public Roads (BPR) function, which is commonly-used for relating travel times to increases in travel volume [3]. The Time Dependent Vehicle Routing Problem (TDVRP) will be studied as a deterministic planning problem taking into account peak hour traffic congestion. Solution methods for the TDVRP have been focused on heuristic approaches [4, 5, 6, 7]. Kok [8] applies a restricted dynamic programming heuristic to solve a TDVRP. In this paper a heuristic algorithm will be presented to solve problem instances of realistic size. Next, this algorithm will be applied to perform a sensitivity analysis to identify which congestion avoiding strategies have a large influence on the objective function. Shippers may adapt the way they plan their transport as a strategy to avoid congestion. For example, time windows at customer locations may be renegotiated, departure times at the depot may be questioned or the assignment of customers to routes and the order in which customers are served may be changed. The proposed methodology will be demonstrated with a Flemish case study.
Research Center/Unit :
Lepur : Centre de Recherche sur la Ville, le Territoire et le Milieu rural - ULiège LEMA - Local Environment Management and Analysis
Disciplines :
Special economic topics (health, labor, transportation...) Civil engineering