Split Delivery Vehicle Routing Problem with Minimum Delivery Amounts.

In the split delivery vehicle routing problem with minimum delivery amounts (SDVRP-MDA), the customer demand can be split among different distribution routes, as long as the quantity delivered to the customer each time remains above the minimum threshold. Despite saving transport cost, the split of customer demand may complicate the order processing and disturb the customer. These problems can be solved satisfactorily by the constraint of the minimum delivery amounts. Therefore, this paper puts forward an adaptive tabu search (ATS) algorithm to solve the SDVRP-MDA. Two new neighbourhood structures are adopted, the adaptive adjustment strategy involving both intensification and diversification search is introduced. The proposed method was tested on 32 standard examples, using 4 different splitting coefficients. On average, the test results only deviated from the current best solution by -0.50~0.22. A total of 94 best solutions were derived and 1 new best solution was obtained. This means our method enjoys good adaptability and robustness. [ABSTRACT FROM AUTHOR]