A Model and Algorithm for the Courier Delivery Problem with Uncertainty

Ilgaz Sungur (), Yingtao Ren (), Fernando Ordóñez (), Maged Dessouky () and Hongsheng Zhong ()
Additional contact information
Ilgaz Sungur: Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089
Yingtao Ren: Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089
Fernando Ordóñez: Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089
Maged Dessouky: Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089
Hongsheng Zhong: UPS, Timonium, Maryland 21093

Transportation Science, 2010, vol. 44, issue 2, 193-205

Abstract: We consider the courier delivery problem (CDP), a variant of the vehicle routing problem with time windows (VRPTW) in which customers appear probabilistically and their service times are uncertain. We use scenario-based stochastic programming with recourse to model the uncertainty in customers and robust optimization for the uncertainty in service times. Our proposed model generates a master plan and daily schedules by maximizing the coverage of customers and the similarity of routes in each scenario, while minimizing the total time spent by the couriers and the total earliness and lateness penalty. To solve large-scale problem instances, we develop an insertion-based solution heuristic, called master and daily scheduler (MADS), and a tabu search improvement procedure. The computational results show that our heuristic improves the similarity of routes and the lateness penalty at the expense of increased total time spent when compared to a solution of independently scheduling each day. Our experimental results also show improvements over current industry practice on two real-world data sets.

Keywords: vehicle routing; robust optimization; stochastic optimization; insertion; tabu search (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (45)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1090.0303 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:44:y:2010:i:2:p:193-205

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().