The fleet size and mix vehicle routing problem with time windows
- PDF / 159,649 Bytes
- 12 Pages / 595 x 842 pts (A4) Page_size
- 75 Downloads / 182 Views
#1999 Operational Research Society Ltd. All rights reserved. 0160-5682/99 $12.00 http://www.stockton-press.co.uk/jor
The ¯eet size and mix vehicle routing problem with time windows F-H Liu and S-Y Shen National Chiao Tung University, Taiwan This paper describes several insertion-based savings heuristics for the ¯eet size and mix vehicle routing problem with time window constraints. A certain number of candidate ¯eet compositions are recorded in the construction phase, followed by applying a composite improvement scheme on them to enhance the solution quality. Computational results on 168 sample problems are reported. We found that heuristics with the consideration of a sequential route construction parameter yielded very good results. In addition, results on the 20 benchmarking problems for the ¯eet and mix vehicle routing problem with no time window constraints also demonstrate the effectiveness of our heuristics. Keywords: vehicle routing; heuristics; time windows; heterogeneous ¯eet
Introduction The classical ¯eet size and mix vehicle routing problem (FSMVRP) is a problem of simultaneously determining the composition and routing of a heterogeneous ¯eet of vehicles in order to service a pre-speci®ed set of customers with known delivery demands from a central depot. Since the temporal aspect of vehicle routing problems has become increasingly important in realistic applications, this study extends the classical FSMVRP by imposing time window constraints on the customers and the central depot. The time window constraints considered in this paper constitute `hard' constraints. That is, a vehicle cannot visit a customer beyond a speci®ed latest starting service time and must wait if it arrives too early at a customer location. Clearly, the FSMVRP with time windows (FSMVRPTW) can also be regarded as a generalisation of the classical vehicle routing problem with time windows (VRPTW). We now state our problem in detail as follows. Let G
V ; A be a directed graph with node set V N [ f0g and arc set A
i; jji 2 V ; j 2 V ; i 6 j, where N
1; 2; . . . ; n denotes the customer set, and node 0 denotes the central depot. With each node i 2 V is associated a demand qi , a service time si and a time window (ai ; bi ) except that q0 and S0 are zero. A distance matrix [di; j ] and a travel time matrix [ti; j ] de®ned on the arc set are known. Moreover, we have a given number of vehicle types with known ®xed costs and known capacities. Each type of vehicles is assumed to be available with in®nite supply. The objective of the FSMVRPTW is to minimise the sum Correspondence: Dr F-H Liu, Department of Industrial Engineering and Management, National Chiao Tung University, Taiwan 300, Republic of China. E-mail: ¯[email protected]
of the vehicle ®xed costs and routing costs such that the following constraints are satis®ed: (1) Each route begins and ends at the central depot; (2) Each customer in N is visited exactly once without violating the time window constraints; (3) The total demand of all customers served on a rout
Data Loading...
