Open vehicle routing problem with cross-docking

• We study the open vehicle routing problem with cross-docking (OVRPCD).
• We propose a simulated annealing (SA) algorithm that incorporates several neighborhood structures to improve the performance on solving OVRPCD.
• Using several neighborhood structures in SA is promising for solving OVRPCD.
• The proposed SA outperforms existing approaches for vehicle routing problem with cross-docking.

The advantages of the cross-docking technique have been increasingly appreciated in literature and in practice. This appreciation, coupled with the advances of numerous applications in the vehicle routing problem (VRP) across numerous practical contexts, presents an opportunity to explore the open VRP with cross-docking (OVRPCD). We introduce a general example in retail wherein the capital expenditure necessary in vehicle acquisition can become a burden for the retailer, who then needs to consider outsourcing a logistics service as a cost-effective option. This practical scenario can be applied to create an open flow network of routes. This study considers a single product and single cross-dock wherein capacitated homogeneous vehicles start at different pickup points and times during pickup operations. The vehicles are scheduled to route in the network synchronously to arrive at the cross-dock center simultaneously. In the delivery operations, all customers must be served at most once and deliveries should be finished within a predetermined duration. We model OVRPCD as a mixed-integer linear program that minimizes the total cost (vehicle hiring cost and transportation cost). A simulated annealing (SA) algorithm is proposed to solve the problem. SA is first verified by solving benchmark instances for the vehicle routing problem with cross-docking and comparing the results with those obtained by existing ​state-of-art algorithms. We then test SA on three sets of OVRPCD benchmark instances and the results are compared with those obtained by CPLEX. Computational results show that both CPLEX and SA can obtain optimal solutions to all small and medium instances. However, the computational time required by SA is shorter than that needed by CPLEX. Moreover, for large instances, SA outperforms CPLEX in both solution value and computational time.