| In the expansion of the classical vehicle routing problem(VRP)with capacity constraints,the multi-compartment vehicle routing problem has been studied extensively in recent years,which can be applied to many scenarios such as fuel distribution,waste recycling,supermarket and convenience store delivery,cold chain fresh product transportation,etc.Firstly,in the context of waste classification and collection,this paper considers a commodity split multi-compartment vehicle routing problem whose objective is to minimize the total transportation cost and attempts to establish a spatio-temporal network flow model with a large number of constraints for the multi-compartment vehicle routing problem.When solving VRP,it is difficult to iteratively optimize the solution of the original problem and the dual problem at the same time as well as to break the symmetry caused by many identical solutions.Moreover,high-quality optimal can be achieved only if the coupling constraints is carefully handled.Currently,the Alternative Direction Method of Multipliers(ADMM)with many good properties has been widely used in the field of convex optimization.It can be seen as a combination of the augmented Lagrangian relaxation and block coordinate descent methods.And ADMM is gaining popularity in machine learning as well.Therefore,in this paper,ADMM is introduced to solve the commodity split multi-compartment vehicle routing problem,and the quadratic penalty term in ADMM is simplified into a simple linear function thanks to the characteristics of binary variables.Besides,a solution framework based on dual decomposition is used to improve the quality of the original and dual solutions iteratively.Finally,this paper selects several cases of different size of customers under the condition of different number of commodities to examine the effectiveness of the proposed algorithm.It is found that this algorithm can achieve an acceptable solution in a reasonable calculation time. |
PDF Full Text Request