Robust Periodic Vehicle Routing Problem with Service Time Uncertainty

The periodic vehicle routing problem (PVRP) has wide applications, such as express service, elevator maintenance and urban waste collection, where customers expect fast response and small delays. The existence of uncertainty has significant influence on the cost and customer experience. Therefore, i...

Full description

Saved in:
Bibliographic Details
Main Authors: Qi, Mingyao, Xiong, Wangqi, Zhou, Qingte, Hua, Shijia
Format: Conference Proceeding
Language:English
Subjects:
Deadline
Elevators
Mathematical model
Optimization
periodic vehicle routing problem
robust optimization
Search problems
Time factors
Uncertainty
variable neighborhood search
Vehicle routing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The periodic vehicle routing problem (PVRP) has wide applications, such as express service, elevator maintenance and urban waste collection, where customers expect fast response and small delays. The existence of uncertainty has significant influence on the cost and customer experience. Therefore, it is crucial to build routes that would be less sensitive to uncertainty. In the paper, we research on the PVRP with service time uncertainty, while no robust optimization for PVRP has been studied before. Each request for service will include an uncertain service time and a deadline for the start of service. We propose the robust model of PVRP with service time uncertainty whose objective is to minimize the overall cost including travel cost, customer's waiting cost and technician's overtime cost. Due to the complexity of the problem, we design a variable neighborhood search algorithm based on worst case to solve it. Numerical experiments prove that: 1) the robust solution has a sufficient immunity against the service time uncertainty; 2) a large uncertainty set parameters might lead to overly conservative robust solution with higher cost.
ISSN:2157-362X
DOI:10.1109/IEEM.2018.8607564