This page is maintained by Zhenzhen Zhang (zhenzhenzhang222@gmail.com) and Lijun Wei (villagerwei@gmail.com) to supplement the article "An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints" Accepted by Transportation Research Part B-Methodological[1].

• To download tables in our paper: ResultFor3LFCVRP.xlsx TableFor3LCVRP.xlsx.
• To download data set: 3LCVRP.zip, 3LFCVRP.zip.
• To download the detailed results: 3LFCVRPResult.zip 3LCVRPResult.zip.
• To download the C++ source code: ELS.zip(Available to Our Team Members Only)

Introduction

This paper introduces and solves a new practical variant of combined routing and loading problem called the capacitated vehicle routing problem minimizing fuel consumption under threedimensional loading constraints (3L-FCVRP). This problem requires to design routes for a fleet of homogeneous vehicles located at the central depot to serve all customers, whose demand are formed by a set of three-dimensional, rectangular, weighted items. Different from the well-studied problem: capacitated vehicle routing problem with 3D loading constraints (3L-CVRP) in literature, the objective of 3L-FCVRP is to minimize the total fuel consumption instead of travel distance. The fuel consumption rate is assumed to be proportionate to the total weight of the vehicle. For any vehicle, assuming the carried load is q, the fuel consumption per unit distance fc(q) is a linear function depending on the total weight of the vehicle, that is fc(q) = a(Q₀ + q) + b, where a and b are constant factors, Q₀ is the self-weight of vehilce and Q is the weight capacity. This formula can be rewritten as fc(q) = fc₀ + (fc* - fc₀)q/Q, where fc₀ = aQ₀ + b is the no-load fuel comsumption rate and fc* = a(Q₀ + Q) + b is the full-load fuel comsumption rate. Thus, the fuel consumption for any edge (i, j) by a vehicle with load q is fc(q) *d_ij.

In 3L-FCVRP, any vehicle must start and terminate at the central depot and each customer must be visited exactly once by one vehicle. In addition, the total weight of the items in one route should not exceed the capacity of the vehicle and a feasible route must satisfy the following constraints in terms of loading aspect:
(1).Loading constraint. Items are loaded with their edges parallel to the sides of the vehicle. Every item has fixed vertical orientation, but horizontal 90-degree rotation is permitted. The length, width and height of each item cannot exceed the space of the vehicle and there is no overlap between any pair of items.
(2).Support constraint. A certain percentage of the item's base must be supported by the vehicle or other items.
(3).Fragility constraint. Items can place on the top of each other except the case that non-fragile item cannot be stacked on any fragile ones.
(4).LIFO constraint. Each item can be unloaded only using a straight movement parallel to L-edge. In other words, for any customer i, no items demanded by other customers visited later than i could be placed above any item I_ik or between I_ik and the rear of the vehicle.

To solve this problem, the evolutionary local search (ELS) framework incorporating with recombination method is employed to explore the solution space and an open space based heuristic is used to examine the feasibility of solutions. In addition, two special data structures Trie and Fibonacci heap are adopted to speed up the procedure. To verify the e ectiveness of our approach, we first test ELS on the instances of 3L-CVRP, which can be seen as a special case of 3L-FCVRP. The results demonstrate that ELS outperforms all existing approaches on average and improves the best known solutions for most of the instances. Then, we generated data for 3L-FCVRP and reported the detailed results of ELS for future comparisons.

Algorithm

Download: ELS.zip

At present, the source codes are only accessible to our team members. We will make it available to public at a later stage.

How to compile and run

To compile, just type ./compile

The executable file created will be called LoadCVRP.

To run the algorithm, you need input four parameters: the instance number(1-39 for 3LCVRP and 3LFCVRP), the constraints version(7 for All constraints, 6 for No support, 5 for No LIFO, 3 for No fragility, 0 for 3D-loading only, then version number +8 is to run 3L-FCVRP), algorithm name(ELS), random seed. For example:

./LoadCVRP 1 15 ELS 1

route 0, cost = 79.2028, customer 2:  14 13
route 1, cost = 112.254, customer 5:  11 2 9 10 5
route 2, cost = 132.232, customer 5:  6 7 8 3 1
route 3, cost = 73.2403, customer 3:  12 4 15
Total cost of solution : 396.929

route 0, customer 2: 
		 CustomerNo: 14	 (w, h, l): 11	12	33	 (x,y,z): 13	0	0	 (x1,y1,z1): 24	12	33
		 CustomerNo: 14	 (w, h, l): 13	14	27	 (x,y,z): 0	16	28	 (x1,y1,z1): 13	30	55
		 CustomerNo: 14	 (w, h, l): 10	8	17	 (x,y,z): 13	12	0	 (x1,y1,z1): 23	20	17
		 CustomerNo: 13	 (w, h, l): 13	17	26	 (x,y,z): 0	0	0	 (x1,y1,z1): 13	17	26
		 CustomerNo: 13	 (w, h, l): 10	11	28	 (x,y,z): 0	17	0	 (x1,y1,z1): 10	28	28
		 CustomerNo: 13	 (w, h, l): 11	16	34	 (x,y,z): 0	0	26	 (x1,y1,z1): 11	16	60

route 1, customer 5: 
		 CustomerNo: 11	 (w, h, l): 15	15	31	 (x,y,z): 8	0	22	 (x1,y1,z1): 23	15	53
		 CustomerNo: 11	 (w, h, l): 13	14	19	 (x,y,z): 8	15	22	 (x1,y1,z1): 21	29	41
		 CustomerNo: 11	 (w, h, l): 16	10	13	 (x,y,z): 8	15	41	 (x1,y1,z1): 24	25	54
		 CustomerNo: 2	 (w, h, l): 8	15	29	 (x,y,z): 0	0	22	 (x1,y1,z1): 8	15	51
		 CustomerNo: 9	 (w, h, l): 24	10	7	 (x,y,z): 0	14	10	 (x1,y1,z1): 24	24	17
		 CustomerNo: 10	 (w, h, l): 25	14	12	 (x,y,z): 0	0	10	 (x1,y1,z1): 25	14	22
		 CustomerNo: 5	 (w, h, l): 15	8	10	 (x,y,z): 0	0	0	 (x1,y1,z1): 15	8	10
		 CustomerNo: 5	 (w, h, l): 13	15	7	 (x,y,z): 0	8	0	 (x1,y1,z1): 13	23	7

route 2, customer 5: 
		 CustomerNo: 6	 (w, h, l): 11	6	27	 (x,y,z): 0	0	33	 (x1,y1,z1): 11	6	60
		 CustomerNo: 6	 (w, h, l): 14	12	12	 (x,y,z): 11	12	33	 (x1,y1,z1): 25	24	45
		 CustomerNo: 6	 (w, h, l): 9	16	20	 (x,y,z): 0	6	33	 (x1,y1,z1): 9	22	53
		 CustomerNo: 7	 (w, h, l): 7	10	23	 (x,y,z): 0	16	0	 (x1,y1,z1): 7	26	23
		 CustomerNo: 7	 (w, h, l): 7	10	21	 (x,y,z): 15	16	0	 (x1,y1,z1): 22	26	21
		 CustomerNo: 8	 (w, h, l): 8	7	27	 (x,y,z): 7	16	0	 (x1,y1,z1): 15	23	27
		 CustomerNo: 8	 (w, h, l): 6	9	31	 (x,y,z): 15	7	0	 (x1,y1,z1): 21	16	31
		 CustomerNo: 8	 (w, h, l): 14	12	15	 (x,y,z): 11	0	36	 (x1,y1,z1): 25	12	51
		 CustomerNo: 3	 (w, h, l): 15	16	33	 (x,y,z): 0	0	0	 (x1,y1,z1): 15	16	33
		 CustomerNo: 3	 (w, h, l): 5	6	36	 (x,y,z): 20	0	0	 (x1,y1,z1): 25	6	36
		 CustomerNo: 1	 (w, h, l): 5	7	30	 (x,y,z): 15	0	0	 (x1,y1,z1): 20	7	30

route 3, customer 3: 
		 CustomerNo: 12	 (w, h, l): 8	9	31	 (x,y,z): 15	0	23	 (x1,y1,z1): 23	9	54
		 CustomerNo: 12	 (w, h, l): 7	7	29	 (x,y,z): 15	9	23	 (x1,y1,z1): 22	16	52
		 CustomerNo: 12	 (w, h, l): 7	14	21	 (x,y,z): 15	16	23	 (x1,y1,z1): 22	30	44
		 CustomerNo: 4	 (w, h, l): 15	17	15	 (x,y,z): 0	0	34	 (x1,y1,z1): 15	17	49
		 CustomerNo: 15	 (w, h, l): 12	18	33	 (x,y,z): 0	0	0	 (x1,y1,z1): 12	18	33
		 CustomerNo: 15	 (w, h, l): 6	9	34	 (x,y,z): 7	18	0	 (x1,y1,z1): 13	27	34
		 CustomerNo: 15	 (w, h, l): 12	9	23	 (x,y,z): 12	0	0	 (x1,y1,z1): 24	9	23

In addition, the total cost, the best time to obtain the result and the total running time are also reported in another file.

Data sets

Below you can get the data sets used in the experiments described in [1]. The data set is the widely used benchmark, and you can download them from 3LCVRP.zip.

Detail results

References