Solving Truck Delivery Problems Using Integrated Evaluation Criteria Based on Neighborhood Degree and Evolutionary Algorithm

摘要

To solve a real-world truck delivery and dispatch problem (TDDP) that involves multiple mutually conflicting objectives, such as running and loading costs, a concept of neighborhood degree (ND) and an integrated evaluation criteria (IEC) of the solution based on ND are proposed. The IEG makes the weight setting easier than by using conventional methods. To find a high-quality solution to a TDDP in practical computational time, an evolutionary algorithm is proposed. It involves 3 components: (i) a simulated annealing (SA)-based method for finding an optimal or a suboptimal route for each vehicle; (ii) an evolutionary computation (EC)-based method for finding an optimal schedule for a group of vehicles; and (iii) threshold-based evolutionary operations, utilizing the ND concept. The TDDP viewed from real-world application is formulated and the proposed algorithm is implemented on a personal computer using C++. The proposed algorithm is evaluated in 2 experiments involving real-world data representative of the TDDP, and applied to food product delivery to a chain of 46 convenience stores in Saitama Prefecture. In the 2 experiments, our proposed algorithm resulted in a better schedule (with 80% -90% shorter computational time) than a schedule produced by an expert. By incorporating application-specific evaluation criteria, the proposed algorithm is applied to problems such as home-delivery of parcels or mail, and to problems of multi-depot delivery and dispatch.