Open AccessTwo-Phase Algorithm to Multiple Depots Vehicle Routing Problem with Soft Time Windows
Author(s) -
Ailing Chen,
Xinxin Gu,
Zhao Gao
Publication year - 2020
Publication title -
iop conference series. earth and environmental science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.179
H-Index - 26
eISSN - 1755-1307
pISSN - 1755-1315
DOI - 10.1088/1755-1315/587/1/012033
Subject(s) - roulette , fitness proportionate selection , vehicle routing problem , genetic algorithm , mathematical optimization , selection (genetic algorithm) , computer science , population , distribution center , operator (biology) , algorithm , distribution (mathematics) , routing (electronic design automation) , mathematics , fitness function , artificial intelligence , repressor , business , computer network , mathematical analysis , chemistry , sociology , biochemistry , geometry , commerce , transcription factor , demography , gene
With the rapid growth of social economy, many companies often have multiple distribution centers. In this paper, multiple depots vehicle routing problem with soft time windows (MDVRPSTW) is researched. A mathematical model, which is aiming to minimize the transport cost, is established. Two-phase algorithm is designed to solve this problem. In the first phase, customers’ orders are distributed to the distribution center by exact algorithm. In the second phase, all the route of each distribution center is calculated. Because this problem is an NP-hard problem, it is difficult to get optimal solution fast when calculating large scale examples, improved genetic algorithm is adopted to solve this problem. In this paper, traditional roulette selection method is abandoned in the stage of designing the selection operator, so as to avoid that the early high fitness individuals occupy the population rapidly and the later population stops evolution due to the small difference of individual fitness. Finally, a practice example of a certain company is calculated by the above method to verify the efficiency of algorithm in this paper.