Genetic Algorithm for the Time-Dependent Vehicle Routing Problem

Abstract

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.

Get full access to this article

View all access options for this article.

References

Bertsimas

D. J.

, and Ryzin

G. V.

. A Stochastic and Dynamic Vehicle Routing in the Euclidean Plane. Operations Research, Vol. 39, No. 4, 1991, pp. 601–615.

Bertsimas

D. J.

, and Ryzin

G. V.

. Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles. Operations Research, Vol. 41, No. 1, 1993, pp. 60–76.

Optimal Policies for Stochastic and Dynamic Vehicle Routing Problems. Ph.D. thesis. Massachusetts Institute of Technology, Cambridge, 1994.

Psaraftis

H. N.

A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem. Transportation Science, Vol. 14, No. 2, 1980, pp. 130–154.

Psaraftis

H. N.

Dynamic Vehicle Routing Problems. In Vehicle Routing: Method and Studies ( Golden

B. L.

and Assad

A. A.

, eds.), North-Holland, Amsterdam, Netherlands, 1988, pp. 223–248.

Swihart

M. R.

A Stochastic and Dynamic Model for the Single Vehicle Dial-A-Ride Problem. Ph.D. thesis. Purdue University, West Lafayette, Ind., 1994.

Bowman

E. H.

Production Scheduling by the Transportation Method of Linear Programming. Operations Research, Vol. 4, 1956, pp. 100–103.

Picard

J. C.

, and Queyranne

. The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling. Operations Research, Vol. 26, No. 1, 1978, pp. 87–110.

Lucena

Time-Dependent Traveling Salesman Problem—The Deliveryman Case. Networks, Vol. 20, 1990, pp. 753–763.

10.

Malandraki

, and Daskin

M. S.

. Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms. Transportation Science, Vol. 26, No. 3, 1992, pp. 185–200.

11.

Malandraki

, and Dial

R. B.

. A Restricted Dynamic Programming Heuristic Algorithm for the Time Dependent Traveling Salesman Problem. European Journal of Operational Research, Vol. 90, 1996, pp. 45–55.

12.

Gen

, and Cheng

. Genetic Algorithms and Engineering Design. John Wiley & Sons, New York, 1997.

13.

Goldberg

, and Lingle

. Alleles, Loci, and the Traveling Salesman Problem. In Proc., 1st International Conference on Genetic Algorithms, Erlbaum, Hillsdale, N.J., 1985.

14.

Uchimura

, and Sakaguchi

. Vehicle Routing Problem Using Genetic Algorithms Based on Adjacency Relations. In Proc., 6th Vehicle Navigation & Information Systems Conference, Seattle, Wash., IEEE, 1995, pp. 214–217.

15.

Chatterjee

, Carrera

, and Lynch

L. A.

. Genetic Algorithms and Traveling Salesman Problems. European Journal of Operational Research, Vol. 93, 1996, pp. 490–510.

16.

Thangiah

S. R.

, and Petrovic

. Introduction to Genetic Heuristics and Vehicle Routing Problems with Complex Constraints. In Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search ( Woodruff

D. L.

, ed.), Kluwer, New York, 1998, pp. 253–286.