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].
IntroductionThis 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(Q0 + q) + b, where a and b are constant factors, Q0 is the self-weight of vehilce and Q is the weight capacity. This formula can be rewritten as fc(q) = fc0 + (fc* - fc0)q/Q, where fc0 = aQ0 + b is the no-load fuel comsumption rate and fc* = a(Q0 + 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) *dij.
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:
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. AlgorithmDownload: 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
The executable file created will be called 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 1The output will produce a *.route file which provides the detailed route and packing information. One solution for 3l_fcvrp01 problem with all constraints is as follows: 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 23The first part is the route information: the cost of route, the serving sequence of customers, followed by the total cost. The second part is the packing results: one line for each item. In each line, the first part is the customer ID which the item belonged to, the next part is the three dimesnsions of the item, and the last two parts are the packing positions of the left-low-bottom and right-high-up corners of the cuboid. In addition, the total cost, the best time to obtain the result and the total running time are also reported in another file. Data setsBelow 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 resultsOur algorithms were implemented as sequential algorithms in C++ and compiled by GCC 4.1.2, and no multi-threading was explicitly utilized. It was executed on an Intel Xeon E5430 clocked at 2.66GHz (Quad Core) with 8 GB RAM running the CentOS 5 linux operating system. Below you can get our output files. You can down all the results file via 3LCVRPResult.zip 3LFCVRPResult.zip.References
Last updated: 1 Apr. 2014, 3 Oct. 2015 by zzz |