| Summary |
The split-delivery vehicle routing problem (SDVRP), in which the demand of a customer can be split and delivered by several vehicles, would result in less cost than the conventional vehicle routing problem. However, split deliveries also incur extra work for logistics operations and undesirable distractions to customers. How to tradeoff cost efficiency and customer service in the split-delivery related problems thus is an important issue. Recently, Gulczynski et al. [29] proposed a variant of the SDVRP called the SDVRP-MDA, in which the customers each require a minimum delivery amount (MDA) every time they are visited. In this dissertation, we propose a new variant of the SDVRP, i.e., the spit-delivery VRP with limited number of deliveries (SDVRP-LND), which considers the number of deliveries for each customer is restrained to kmax.
We propose a unified multi-start heuristic method, i.e., SRC+IMP (Split-delivery Route Construction + solution IMProvement), to solve the SDVRP and its variants of the SDVRP-MDA and the SDVRP-LND. The initial-solution generator SRC adaptively applies either node-insertion or route-addition procedures, which were designed specifically for the SDVRP and its variants, to generate an initial solution. The IMP conducts local search with multiple neighborhoods for solution improvement, in which we developed a novel node ejection-chain operator for the split-delivery related problems. The overall SRC+IMP combines the SRC and the IMP modules to implement a multi-start solution procedure with a single parameter to control the restart.
The proposed SRC+IMP algorithms are tested with all the related benchmark problems. We conduct the IMP module with two variable neighborhood descent methods, i.e., VND and RVND. It is found that the performance of the SRC+RVND is better than that of the SRC+VND. The results of the SRC+RVND for the SDVRP show that, out of 32 instances tested, the average deviation from the best known solutions (BKS) is 0.36%, which is only second to the ILS algorithm (Silva et al. [44]). For the SDVRP-MDA, out of the 128 instances tested, the results reveal 81 BKS and 36 new best solutions; the average deviation is -0.27%. For the SDVRP-LND, out of the 22 instances tested, we find 5 BKS and 5 new best solutions; the average deviation is 0.07%.
We also investigate the impact of kmax to the potential cost saving of the SDVRP-LND. It is found that, for kmax=3, the average cost saving is 4.11%, which is only 0.06% less than that of the SDVRP. This implies that the SDVRP-LND with kmax=3 can provide a valuable and easy-to-implement tool for logistics operations. |
