Given a graph whose arc traversal times vary over time, the time-dependent travelling salesman problem (TDTSP) consists in finding a Hamiltonian tour of least total duration covering the vertices of the graph. The contribution of this paper is twofold. First, …
In urban areas, logistic transportation operations often run into problems because travel speeds change, depending on the current traffic situation. If not accounted for, time-dependent and stochastic travel speeds frequently lead to missed time windows and thus poorer service. Especially …
In this paper we exploit some properties of the travel time model proposed by Ichoua, Gendreau, and Potvin [Ichoua S, Gendreau M, Potvin J-Y (2003) Vehicle dispatching with time-dependent travel times. Eur. J. Oper. Res. 144:379–396], on which most of …
The minimum cost path problem in a time-varying road network is a complicated problem. The paper proposes two heuristic methods to solve the minimum cost path problem between a pair of nodes with a time-varying road network and a congestion …
Today manufacturers have become much more concerned with the coordination of both manufacturing (of new products) and recycling (of reusable resources) operations. This requires simultaneous scheduling of both forward and reverse flows of goods over a supply chain network. This …
Metaheuristic algorithms, such as simulated annealing and tabu search, are popular solution techniques for vehicle routing problems (VRPs). These approaches rely on iterative improvements to a starting solution, involving slight alterations to the routes (ie, neighbourhood moves), moving a node …
A number of technological advances have led to a renewed interest in dynamic vehicle routing problems. This survey classifies routing problems from the perspective of information quality and evolution. After presenting a general description of dynamic routing, we introduce the …
This paper studies the problem of computing optimal journeys in dynamic public transit networks. We introduce a novel algorithmic framework, called Connection Scan Algorithm (CSA), to compute journeys. It organizes data as a single array of connections, which it scans …
A new problem is introduced named the Time-Dependent Prize-Collecting Arc Routing Problem (TD-PARP). It is particularly relevant to situations where a transport manager has to choose between a number of full truck load pick-ups and deliveries on a road network …
This paper presents a branch-and-price algorithm for the time-dependent vehicle routing problem with time windows (TDVRPTW). We capture road congestion by considering time-dependent travel times, i.e., depending on the departure time to a customer, a different travel time is incurred. …