Ing. Logistica Y Transporte

Computers & Operations Research 34 (2007) 2734 – 2742 www.elsevier.com/locate/cor

A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem
Feiyue Lia , Bruce Goldenb,∗ , Edward Wasilc
a Princeton Optimization Inc., 2 Research Way, Princeton, NJ 08540, USA b R.H. Smith School of Business, University of Maryland, College Park, Maryland 20742, USA c KogodSchool of Business, American University, Washington, DC 20016, USA

Available online 19 January 2006

Abstract In the heterogeneous fleet vehicle routing problem (HVRP), several different types of vehicles can be used to service the customers. The types of vehicles differ with respect to capacity, fixed cost, and variable cost. We assume that the number of vehicles of each type is fixed and equalto a constant. We must decide how to make the best use of the fixed fleet of heterogeneous vehicles. In this paper, we review methods for solving the HVRP, develop a variant of our record-to-record travel algorithm for the standard vehicle routing problem that takes a heterogeneous fleet into account, and report computational results on eight benchmark problems. Finally, we generate a new set of fivetest problems that have 200–360 customers and solve each new problem using our record-to-record travel algorithm. 2005 Elsevier Ltd. All rights reserved.
Keywords: Vehicle routing problem; Heuristics; Record-to-record travel

1. Introduction In the standard version of the vehicle routing problem (VRP), a fleet of homogeneous vehicles is based at a single depot. Each vehicle has the same capacityand must leave from and return to the depot. Each customer has a known demand and is serviced by exactly one visit of a single vehicle. A sequence of deliveries must be generated for each vehicle so that all customers are serviced and the total distance traveled by the fleet is minimized. In the heterogeneous fleet vehicle routing problem (HVRP), there are several different vehicle types. Forvehicle type t, the capacity is Qt , the fixed cost is ft , and the variable cost per unit distance is t . There are nt vehicles of type t that are available for servicing the customers. Note that nt might be very large or, essentially, unlimited. Some customers may have such large demands that they can be serviced only by large capacity vehicles. In the fixed fleet version of the HVRP, the values of ntare fixed. More specifically, the number of vehicles of type t is limited and the fleet composition is known in advance. We must decide how to make the best use of a fixed fleet of heterogeneous vehicles. This is the version of the HVRP studied in this paper.

∗ Corresponding author. Tel.: +1 301 405 2232; fax: +1 301 405 3364.

E-mail address: bgolden@rhsmith.umd.edu (B. Golden). 0305-0548/$ - seefront matter doi:10.1016/j.cor.2005.10.015 2005 Elsevier Ltd. All rights reserved.

F. Li et al. / Computers & Operations Research 34 (2007) 2734 – 2742

2735

When the number of vehicles of type t is unlimited, we must determine the best composition of the fleet. We are not studying this version of the HVRP in this paper and refer the reader to [1] for a literature review and computationalresults with a tabu search heuristic. In practice, there are several applications of the fixed fleet HVRP according to [2]. In residential and commercial waste collection, it is common for fleets to have different capacity vehicles. In residential pickups, when the actual service at a location must be completed by a specific vehicle such as a side loader with mechanical arms that pick up the trashcans, there are site dependency issues rather than the vehicle capacity issues encountered in the HVRP (see [3]) for details on the VRP with site dependencies). Levy [2] points out that FedEx Ground has different capacity vehicles in its fleet with vehicles oriented to bulk, ground contractors, and home delivery contractors. The capacity of the different vehicles is taken into account in a fleet mix...