A Dynamic Strategy for Home Pick-Up Service with Uncertain Customer Requests and Its Implementation

Yu Wu, Bo Zeng and Siming Huang
Additional contact information
Yu Wu: Institutes of Science and Development, Chinese Academy of Sciences, Beijing 100190, China
Bo Zeng: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, PA 15261, USA
Siming Huang: Institutes of Science and Development, Chinese Academy of Sciences, Beijing 100190, China

Sustainability, 2019, vol. 11, issue 7, 1-21

Abstract: In this paper, a home service problem is studied, where a capacitated vehicle collects customers’ parcels in one pick-up tour. We consider a situation where customers, who have scheduled their services in advance, may call to cancel their appointments, and customers, who do not have appointments, also need to be visited if they request for services as long as the capacity is allowed. To handle those changes that occurred over the tour, a dynamic strategy will be needed to guide the vehicle to visit customers in an efficient way. Aimed at minimizing the vehicle’s total expected travel distance, we model this problem as a multi-dimensional Markov Decision Process (MDP) with finite exponential scale state space. We exactly solve this MDP via dynamic programming, where the computing complexity is exponential. In order to avoid complexity continually increasing, we aim to develop a fast looking-up method for one already-examined state’s record. Although generally this will result in a huge waste of memory, by exploiting critical structural properties of the state space, we obtain an O ( 1 ) looking-up method without any waste of memory. Computational experiments demonstrate the effectiveness of our model and the developed solution method. For larger instances, two well-performed heuristics are proposed.

Keywords: home service; pick up; routing; Markov decision process (MDP); dynamic programming; uncertain request; service cancellation (search for similar items in EconPapers)
JEL-codes: O13 Q Q0 Q2 Q3 Q5 Q56 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2071-1050/11/7/2060/pdf (application/pdf)
https://www.mdpi.com/2071-1050/11/7/2060/ (text/html)

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:gam:jsusta:v:11:y:2019:i:7:p:2060-:d:220652

Access Statistics for this article

Sustainability is currently edited by Ms. Alexandra Wu

More articles in Sustainability from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().