Vehicle Routing Problem Solving Method for a Cooperative Logistics Network by Using Multi-Stage GA
This paper proposes a method of solving the Vehicle Routing Problem (VRP) for a cooperative logistics network that many enterprises take part in. Logistics cooperation over multiple enterprises that belong to a single supply chain can effectively improve the logistics efficiency. To build such a cooperative logistics network as Fig. 1, an operation schedule of each depot is required to evaluate the accurate logistics cost based on the number of used vehicle. A simple mathematical optimal schedule is not usually readily accepted because of conflicts that arise in the different enterprises. Moreover, a change in the operation schedule exerts a detrimental influence on the shipping schedules of parts suppliers and the production plans of factories. Thus, this network needs a stable schedule that can deal with fluctuation in the amount of the load. A method of solving the VRP that can obtain a human expert level solution to achieve steady logistics operation within interactive response time is required to optimize a cooperative logistics network. To satisfy this requirement, a scheduling model for the cooperative logistics network and a multi-stage GA are proposed. The multi-stage GA enables to obtain an accurate solution under both hard and weak time constraints. Moreover, the evaluation method for each individual based on the proposed model can generate a delivery schedule that enables stable logistics operation. The delivery schedule in our problem has to satisfy both the time constraints and the load capacity constraints. However, it is difficult to construct a method of solving the above two constraints simultaneously. Thus, a multi-stage GA combines a time constraint preferred GA with a load capacity constraint preferred GA. To obtain a more accurate solution than a single GA, two GAs are implemented for each effective phase. To construct a stable delivery schedule, an evaluation method includes fluctuation of shipping load. That is, this method uses the average volume of load to check the vehicle capacity constraints at the individual’s reconstruction. Furthermore, to calculate the fitness value of each individual, a cost of extra vehicles is added to the value. To evaluate the accuracy of the proposed method, we applied it to the VRP benchmark problem. We compared the following four methods. 1) Time constraint preferred type GA, 2) Load capacity preferred type GA, 3) Mixed GA, and 4) Multi-stage GA. Table 1 lists the accuracy of each method. The multi-stage GA obtained the solution with less than 6.0% error for both problems. To evaluate the stability of the logistics operation for the schedules generated by the proposed method, we examined a case where 100% of the shipments by the parts supplier had changed. We generated the delivery schedules from one hundred suppliers to a depot using the five method below and evaluated the number of regulary operated vehicles and extra vehicles. 1) Average method, 2) Average+20% method 3)Maximum method, 4) Optimal method, and 4) Proposed method. Table 2 shows that the proposed scheduling needed 35 more regular vehicles than average scheduling. However, the proposed scheduling only needs 23 extra vehicles. The total cost of the proposed scheduling method is less than that of the other four methods, because the cost of an extra vehicle is higher than a regular vehicle.