A mathematical model is formulated for the time-dependent vehicle routing problem (TDVRP) and a genetic algorithm (GA) is proposed for solving it. Formulation of the problem considers multiple vehicles with different capacities, pick-up or delivery demands with soft time windows, real-time service requests, and real-time variations in travel times between demand nodes. The objective is to minimize the total cost, which consists of routing cost, fixed cost for using the vehicles, and customer inconvenience costs. A mixed-integer linear programming formulation of the TDVRP is presented. Like other combinatorial problems, to solve the TDVRP exactly, a significant amount of processing time is required. A GA is proposed to solve the problem. The proposed GA was tested on the test problems, and GA results were compared with the exact solutions for small test problems. GA results were also compared with the lower bounds obtained for the solution of the larger problems. In the case of small problems, only 2 of 33 cases have gaps between the GA solutions and the exact solutions, and the maximum gap is less than 5 percent. For larger problems, the maximum gaps between GA solutions and lower bound solutions are less than 7 percent.
Genetic Algorithm for the Time-Dependent Vehicle Routing Problem
Transportation Research Record: Journal of the Transportation Research Board
Transportation Research Record: Journal of the Transportation Research Board ; 1771 , 1 ; 164-171
2001-01-01
Article (Journal)
Electronic Resource
English
Genetic Algorithm for the Time-Dependent Vehicle Routing Problem
Online Contents | 2001
|Genetic Algorithm for the Time-Dependent Vehicle Routing Problem
British Library Conference Proceedings | 2001
|Solving Vehicle Routing Problem with Time Windows by Genetic Algorithm
British Library Conference Proceedings | 2002
|Time-Dependent Green Vehicle Routing Problem
Springer Verlag | 2020
|