Knowledge-Guided Neighborhood Search Algorithm for Close-Open Vehicle Routing Problem
A realistic variant of conventional vehicle routing problems, which simultaneously considers the open and close routes in the solution of the problem, is introduced in this paper. The objective is to obtain the optimal routing planning and minimize the to
- PDF / 155,019 Bytes
- 7 Pages / 439.36 x 666.15 pts Page_size
- 34 Downloads / 166 Views
Abstract A realistic variant of conventional vehicle routing problems, which simultaneously considers the open and close routes in the solution of the problem, is introduced in this paper. The objective is to obtain the optimal routing planning and minimize the total costs for operating the open and close routes. A knowledgeguided neighborhood search (KGNS) algorithm is designed to handle this vehicle routing problem, and the results of experiments show that the proposed KGNS algorithm can effectively produce the satisfied solutions. Keywords Vehicle routing problem · Close-open vehicle routing · Knowledge-guided neighborhood search algorithm
1 Introduction With the development of Internet economy, logistics and distribution companies can easily hire vehicles from the online platform. Therefore, these companies will no longer to keep a large number of private vehicles, which leads to that the companies often uses private vehicles and hired vehicles to complete the distribution task together. Under normal circumstances, the private vehicles need to return to the depot after completing their tasks, but the hired vehicles are not required, i.e. the coexistence of close and open vehicle routing problems has emerged. Since the vehicle routing problem (VRP) was introduced sixty years ago by Dantzig and Ramser [1], both close vehicle routing problems (Close-VRP) and open vehicle routing problems (Open-VRP) have been widely studied, the recent researches on VRP can be referred to the literature reviews [2–4]. However, the combined considerations of Close-VRP and Open-VRP are not common. To the
G.-J. Sun () College of Economic and Management, Zhejiang Normal University, Jinhua, China e-mail: [email protected] © The Editor(s) (if applicable) and The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd. 2020 X. Li, X. Xu (eds.), Proceedings of the Seventh International Forum on Decision Sciences, Uncertainty and Operations Research, https://doi.org/10.1007/978-981-15-5720-0_18
157
158
G.-J. Sun
best of our knowledge, the close-open mixed vehicle routing problem (COMVRP) was put forward by Liu and Zhang [5] for the first time, the objective of their COMVRP model is to minimize the fixed and variable costs for operating the open and close routes, and designed an effective memetic algorithm to solve their COMVRP model. Brito et al. [6] improved and extended the formulation COMVRP model proposed by Liu and Zhang [5] via considering precise time windows, and introduced a variable neighbourhood search procedures to solve their proposed VRP model. Meanwhile, Brito et al. [7] also proposed a close-open vehicle routing model with imprecise factors, in which the capacity and time windows constraints are considered flexible and modelled as fuzzy constraints. Alinaghian et al. [8] developed a close-open vehicle routing model with delivery section which adopting close route and pickup section which using open route, and they assumed that the nodes can be visited by more than one vehicle. Azadeh and Farrokhi-Asl [
Data Loading...
