A combined order selection and time-dependent vehicle routing problem with time widows for perishable product delivery

• Published in: Computers & industrial engineering 2017-12, Vol.114, p.101-113
• Main Authors: Ma, Zu-Jun, Wu, Yao, Dai, Ying
• Format: Article
• Language: English
• Subjects: Ant colony algorithm; Large neighborhood search; Order selection; Perishable products; Time-dependent; Vehicle routing problem
• ISSN: 0360-8352; 1879-0550
• DOI: 10.1016/j.cie.2017.10.010

•A MIP model is developed for COSTDVRPTW in the delivery of perishable products.•Customers’ time windows and floating time windows are considered simultaneously.•A hybrid ant colony algorithm comprising local search operators is proposed.•The impact of penalties from order rejection is analyzed.•The impact of time-dependent travel times is analyzed. This paper addresses a real-life delivery problem often encountered by urban perishable product deliverers, in which the providers suffer losses from failed delivery, such as product deterioration or violating customers’ time windows, especially when delivery orders accepted are beyond the providers’ delivery capacity. To the best of our knowledge, traditional delivery models are not applicable in such cases and few papers are related. Hence, we develop a new model that combines order selection and time-dependent vehicle routing problem with time windows in the same framework of perishable product delivery, to decide the delivery order, the service sequence and the timing to start a delivery task with the objective of profit maximization. Furthermore, a hybrid ant colony algorithm comprising local search operators is proposed. The effectiveness of our model and algorithm is demonstrated with several computational experiments, and some management insights are provided to guild practical operations.