Capacitated Arc Routing Problem With Simultaneous Pickups And Deliveries

The traditional Capacitated Arc Routing Problem (CARP) considers eitherpickup or delivery process during the operation. It was widely used in real-worldapplications, including for instance post-delivery, urban waste collection and soon. Along with the widely spread of reverse logistics in current business ofexpress delivery, reverse logistics is added into the CARP. The Capacitated ArcRouting Problem with Simultaneous Pickups and Deliveries (CARPSPD) isdiscussed in this paper, including four sections:Firstly, a lot of literatures about Vehicle Routing Problem with Backhauling,Vehicle Routing Problems with Mixed Backhauling, Vehicle Routing Problemwith Simultaneous Pickup and Delivery were reviewed, and the algorithms aswell as the unsolved problems were analyzed, which forms the basement for theresearch.Secondly, a basic mathematical model is established based on detail analysisof the problem, and two kinds of demand are added into the model. Stronglyfeasible tour and weakly feasible tour are defined as well as the methodconverting from weakly feasible tour into strongly feasible one in this paper.Thirdly, a Path-scanning heuristic with ellipse rule (PSA) and a variableneighborhood search algorithm (VNS) are designed for this problem. A weaklyfeasible solution is built by PSA in the former, which is then transformed intostrongly feasible one. Especially for the VNS, a hybrid local search with fourkinds of neighborhood structure is designed, and a hierarchical local searchstrategy is adopted to expend the search area of the algorithm.Lastly, test collections of the CARPSPD are created from the benchmarkfiles of CARP. Experimental results on these test collections show that VNS cansolve CARPSPD more efficiently than PSA, with respect to stability and qualityof solutions.