Vehicle routing is an important combinatorial optimization problem. In real transport networks,the travel speed and travel time of roads have large time-variability and randomness. The study of vehicle routing problem in time-dependent network has even more practical value than static …
This paper describes a dynamic capacitated arc routing problem motivated from winter gritting applications. In this problem, the service cost on each arc is a piecewise linear function of the time of beginning of service. This function also exhibits an …
In recent years, many speed-up techniques for Dijkstra’s algorithm have been developed that make the computation of shortest paths in static road networks a matter of microseconds. However, only few of those techniques work in time-dependent networks which, unfortunately, appear …
This paper presents an Ant Colony System algorithm hybridized with insertion heuristics for the Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW). In the TDVRPTW a fleet of vehicles must deliver goods to a set of customers, time window constraints …
Tramp shipping companies are committed to transport a set of contracted cargoes and try to derive additional revenue from carrying optional spot cargoes. Traditionally, models for ship routing and scheduling problems are based on fixed speed and a given fuel …
The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditional TSP where the travel cost between two cities depends on the moment of the day the arc is travelled. In this paper, we focus on the case where …
This paper proposes a variable neighborhood descent heuristic for solving a capacitated arc routing problem with time-dependent service costs. The problem is motivated by winter gritting applications where the timing of each intervention is crucial. The variable neighborhood descent is …
We show how to route on very large public transportation networks (up to half a billion arcs) with average query times of a few milliseconds. We take into account many realistic features like: traffic days, walking between stations, queries between …
Traditional technologies, such as inductive loop detectors, do not usually produce measurements of the quality required by real-time applications. Therefore, one wonders what could be expected from newer information and communication technologies, such as automatic vehicle location, license plate recognition, …
A heuristic algorithm is described for vehicle routing and scheduling problems to minimise the total travel time, where the time required for a vehicle to travel along any road in the network varies according to the time of travel. The …