Dynamic Vehicle Routing Problem with Multiple Objectives

Abstract

This paper addresses a dynamic vehicle routing problem related to courier mail services with explicit consideration of multiple objectives. This problem is modeled as a dynamic traveling repairman problem with time windows, and with three objectives considered: maximization of the number of serviced customers, minimization of customer waiting, and minimization of total travel time. A solution (simulation) framework, extending techniques developed for single-objective dynamic routing problems in the literature, is proposed to tackle this multiobjective problem. An efficient chained local search heuristic is embedded in this solution framework to solve the underlying static problem, the traveling salesman problem with time windows. Comprehensive simulation experiments conducted on data sets derived from benchmark problems show that the proposed algorithmic approach is able to provide high-quality solutions with limited computing effort. These experiments also indicate that the multiobjective model proposed in this study can offer much more attractive solutions to decision makers than single-objective models.

Get full access to this article

View all access options for this article.

References

Psaraftis

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

and Assad

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

Psaraftis

Dynamic Vehicle Routing: Status and Prospects. Annals of Operations Research, Vol. 61, 1995, pp. 143–164.

Bertsimas

and Van Ryzin

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

Bertsimas

and Van Ryzin

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

Psaraftis

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

Psaraftis

An Exact Algorithm for the Single Vehicle Many-to-Many Dial-a-Ride Problem with Time Windows. Transportation Science, Vol. 17, 1983, pp. 351–357.

Ichoua

Gendreau

and Potvin

J.-Y.

Diversion Issues in Real-Time Vehicle Dispatching. Transportation Science, Vol. 34, 2000, pp. 426–438.

Ichoua

Gendreau

and Potvin

J.-Y.

Vehicle Dispatching with Time-Dependent Travel Times. European Journal of Operational Research, Vol. 144, 2003, pp. 379–396.

Mitrović-Minić

Krishnamurti

and Laporte

Double-Horizon Based Heuristics for the Dynamic Pickup and Delivery Problem with Time Windows. Transportation Research Part B, Vol. 38, 2004, pp. 669–685.

10.

Larsen

Madsen

and Solomon

Partially Dynamic Vehicle Routing—Models and Algorithms. Journal of the Operational Research Society, Vol. 53, 2002, pp. 638–646.

11.

Bent

R. W.

and Van Hentenryck

Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers. Operations Research, Vol. 52, No. 6, 2004.

12.

Gendreau

Guertin

Potvin

J.-Y.

and Séguin

Neighborhood Search Heuristics for a Dynamic Vehicle Dispatching Problem with Pickups and Deliveries. Technical Report CRT-98-10. Centre de Recherche sur les Transports, University of Montreal, Quebec, Canada, 1998.

13.

Gendreau

Guertin

Potvin

J.-Y.

and Taillard

Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching. Transportation Science, Vol. 33, 1999, pp. 381–390.

14.

Gendreau

and Potvin

J.-Y.

Dynamic Vehicle Routing and Dispatching. In Fleet Management and Logistics ( Crainic

and Laporte

, eds.), Kluwer Academic Publishers, Boston, 1998, pp. 115–126.

15.

Ghiani

Guerriero

Laporte

and Musmanno

Real-Time Vehicle Routing: Solution Concepts, Algorithms and Parallel Computing Strategies. Technical Report. Center of Excellence for High Performance Computing, University of Calabria, Italy, 2003.

16.

Regan

A. C.

Mahmassani

H. S.

and Jaillet

Dynamic Decision Making for Commercial Fleet Operations Using Real-Time Information. In Transportation Research Record 1537, TRB, National Research Council, Washington, D.C., 1996, pp. 91–97.

17.

Powell

A Stochastic Formulation of the Dynamic Assignment Problem, with an Application to Truckload Motor Carriers. Transportation Science, Vol. 30, 1996, pp. 195–219.

18.

Powell

Jaillet

and Odoni

Stochastic and Dynamic Networks and Routing. In Network Routing, Handbooks in Operations Research and Management Science, Vol. 8 ( Ball

Magnanti

Monma

and Nemhauser

, eds.), North-Holland, Amsterdam, 1995, pp. 141–295.

19.

Keeney

and Raiffa

Decisions with Multiple Objectives: Preferences and Value Trade-offs. Cambridge University Press, Cambridge, U.K., 1993.

20.

Ignizio

and Cavalier

Linear Programming. Prentice Hall, Upper Saddle River, N.J., 1994.

21.

Kontoravdis

and Bard

A GRASP for the Vehicle Routing Problem with Time Windows. ORSA Journal on Computing, Vol. 7, 1995, pp. 10–23.

22.

Applegate

Cook

and Rohe

Chained Lin-Kernighan for Large Scale Traveling Salesman Problems. INFORMS Journal on Computing, Vol. 15, 2003, pp. 82–92.

23.

Solomon

Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, Vol. 35, 1987, pp. 254–265.

24.

Ascheuer

Fischetti

and Grötschel

Solving the Asymmetric Traveling Salesman Problem with Time Windows by Branch-and-Cut. Mathematical Programming, Vol. 90, 2001, pp. 475–506.

25.

Mingozzi

Bianco

and Ricciardelli

Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints. Operations Research, Vol. 45, 1997, pp. 365–377.