Artificial immune algorithm for multi-depot vehicle scheduling problems

Zhongyi Wu; Donggen Wang; Linyuan Xia; Xiaoling Chen

doi:10.1117/12.812864

5 November 2008 Artificial immune algorithm for multi-depot vehicle scheduling problems

Zhongyi Wu, Donggen Wang, Linyuan Xia, Xiaoling Chen

Proceedings Volume 7144, Geoinformatics 2008 and Joint Conference on GIS and Built Environment: The Built Environment and Its Dynamics; 714436 (2008) https://doi.org/10.1117/12.812864
Event: Geoinformatics 2008 and Joint Conference on GIS and Built Environment: Geo-Simulation and Virtual GIS Environments, 2008, Guangzhou, China

Abstract

In the fast-developing logistics and supply chain management fields, one of the key problems in the decision support system is that how to arrange, for a lot of customers and suppliers, the supplier-to-customer assignment and produce a detailed supply schedule under a set of constraints. Solutions to the multi-depot vehicle scheduling problems (MDVRP) help in solving this problem in case of transportation applications. The objective of the MDVSP is to minimize the total distance covered by all vehicles, which can be considered as delivery costs or time consumption. The MDVSP is one of nondeterministic polynomial-time hard (NP-hard) problem which cannot be solved to optimality within polynomial bounded computational time. Many different approaches have been developed to tackle MDVSP, such as exact algorithm (EA), one-stage approach (OSA), two-phase heuristic method (TPHM), tabu search algorithm (TSA), genetic algorithm (GA) and hierarchical multiplex structure (HIMS). Most of the methods mentioned above are time consuming and have high risk to result in local optimum. In this paper, a new search algorithm is proposed to solve MDVSP based on Artificial Immune Systems (AIS), which are inspirited by vertebrate immune systems. The proposed AIS algorithm is tested with 30 customers and 6 vehicles located in 3 depots. Experimental results show that the artificial immune system algorithm is an effective and efficient method for solving MDVSP problems.

Citation Download Citation

Zhongyi Wu, Donggen Wang, Linyuan Xia, and Xiaoling Chen "Artificial immune algorithm for multi-depot vehicle scheduling problems", Proc. SPIE 7144, Geoinformatics 2008 and Joint Conference on GIS and Built Environment: The Built Environment and Its Dynamics, 714436 (5 November 2008); https://doi.org/10.1117/12.812864

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available