Robust Dynamic Vehicle Routing Optimization with Time Windows
Hard time window and randomly appeared dynamic clients are two key issues in dynamic vehicle routing problems. In existing planning methods, when the new service demand came up, global vehicle routing optimization method was triggered to find the optimal
- PDF / 513,361 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 62 Downloads / 254 Views
Abstract. Hard time window and randomly appeared dynamic clients are two key issues in dynamic vehicle routing problems. In existing planning methods, when the new service demand came up, global vehicle routing optimization method was triggered to find the optimal routes for non-served clients, which was time-consuming. Therefore, robust dynamic vehicle routing method based on local optimization strategies is proposed. Three highlights of the novel method are: (i) After constructing optimal robust virtual routes considering all clients, static vehicle routes for fixed clients are formed by removing all dynamic clients from robust virtual routes. (ii) The dynamically appeared clients append to be served according to their service demands and the vehicles’ locations. Global vehicle routing optimization is triggered only when no suitable locations can be found for dynamic clients. (iii) A metric measuring the algorithms’ robustness is given. The statistical results indicated that the routes obtained by the proposed method have better stability and robustness, but may be sub-optimum. Moreover, time-consuming global vehicle routing optimization is avoided as dynamic clients appear. Keywords: Robust Dynamic Ant colony algorithm
Vehicle routing problem Time windows
1 Introduction The dynamic vehicle routing problem with time windows is the most practical and complex problem among the vehicle routing problems. Its goal is to find the optimal vehicle routes having the shortest driving distance or the least transport cost [1]. During the delivery cycle, as dynamic clients request new service demands, the distribution center needs to design the vehicles’ routes in terms of their real-time location and the specific time windows of dynamic clients [2]. The time window limits the start and ending time of client’s delivery tasks. It normally is divided into hard time windows and soft time windows [3]. We focus on dynamic vehicle routing problem with hard time windows. For hard time windows, the vehicle must arrive at the client earlier than the ending time. Otherwise, the delivery task is failed. If the vehicle reaches the client earlier than the start time, it shall wait for a while, which increases the time cost. Many researches had been done to introduce intelligent optimization algorithms, such as ant colony algorithm, genetic algorithm, particle swarm optimization, to solve © Springer International Publishing Switzerland 2016 Y. Tan et al. (Eds.): ICSI 2016, Part II, LNCS 9713, pp. 28–36, 2016. DOI: 10.1007/978-3-319-41009-8_4
Robust Dynamic Vehicle Routing Optimization
29
dynamic vehicle routing problem. Taillard and Badeau [4] proposed double ant colony system. Two colonies relying on independent pheromone respectively optimized two objective functions and shared the optimal routes during the evolution process. By adopting tabu search algorithm [5], a client was removed from one route and inserted into another vehicle’s route with minimum cost in each iteration. Taniguchi et al. [6] adjusted and optimized the exi
Data Loading...
