Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads

• We formulate the multi-commodity unpaired pickup and delivery vehicle routing problem with split loads.
• We develop an easy-to-implement heuristic in order to gain an efficient feasible solution quickly for the problem.
• A local search algorithm based on the variable neighborhood search method is developed to improve the feasible solution.
• The algorithm can obtain solutions which are identical or close to the optimal ones for problems with relatively large size.

This paper addresses the routing problem with unpaired pickup and delivery with split loads. An interesting factor of our problem is that the quantity and place for pickup and delivery are decision variables in the network. We develop an easy-to-implement heuristic in order to gain an efficient and feasible solution quickly. Then, a local search algorithm based on the variable neighborhood search (VNS) method is developed to improve the performance of the heuristic. Computational results show that the proposed VNS method is able to obtain an optimal or near optimal solution in reasonable time for the formulated problem.