Robust vehicle routing problem with deadlines and travel time/demand uncertainty

C Lee, K Lee and S Park
Additional contact information
C Lee: ETRI, Daejeon, Republic of Korea
K Lee: Hankuk University of Foreign Studies, Gyeonggi-do, Republic of Korea
S Park: KAIST, Daejeon, Republic of Korea
Authors registered in the RePEc Author Service: Cheng Few Lee

Journal of the Operational Research Society, 2012, vol. 63, issue 9, 1294-1306

Abstract: In this article, we investigate the vehicle routing problem with deadlines, whose goal is to satisfy the requirements of a given number of customers with minimum travel distances while respecting both of the deadlines of the customers and vehicle capacity. It is assumed that the travel time between any two customers and the demands of the customer are uncertain. Two types of uncertainty sets with adjustable parameters are considered for the possible realizations of travel time and demand. The robustness of a solution against the uncertain data can be achieved by making the solution feasible for any travel time and demand defined in the uncertainty sets. We propose a Dantzig-Wolfe decomposition approach, which enables the uncertainty of the data to be encapsulated in the column generation subproblem. A dynamic programming algorithm is proposed to solve the subproblem with data uncertainty. The results of computational experiments involving two well-known test problems show that the robustness of the solution can be greatly improved.

Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (33)

Downloads: (external link)
http://www.palgrave-journals.com/jors/journal/v63/n9/pdf/jors2011136a.pdf Link to full text PDF (application/pdf)
http://www.palgrave-journals.com/jors/journal/v63/n9/full/jors2011136a.html Link to full text HTML (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:63:y:2012:i:9:p:1294-1306

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().