Paper:
Views over last 60 days: 553
Solving Truck Delivery Problems Using Integrated Evaluation Criteria Based on Neighborhood Degree and Evolutionary Algorithm
Fangyan Dong*, Kewei Chen**, Eduardo Masato Iyoda*, Hajime Nobuhara*, and Kaoru Hirota*
*Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, G3-49, 4259, Nagatsuta, Midori-ku, Yokohama 226-8502, Japan
**Computing Technology Driving Laboratory, Fujimi 1-6-14-605, Kawasaki-ku, Kawasaki 210-0011, Japan
Received:February 27, 2004Accepted:April 16, 2004Published:May 20, 2004
Keywords:truck delivery and dispatch problem (TDDP), optimal solution, evaluation criteria, evolutionary computation, simulated annealing
Abstract
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 IEC 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 multidepot delivery and dispatch.
Cite this article as:F. Dong, K. Chen, E. Iyoda, H. Nobuhara, and K. Hirota, “Solving Truck Delivery Problems Using Integrated Evaluation Criteria Based on Neighborhood Degree and Evolutionary Algorithm,” J. Adv. Comput. Intell. Intell. Inform., Vol.8 No.3, pp. 336-345, 2004.Data files:
