Lookahead scenario relaxation for dynamic time window assignment in service routing

Rosario Paradiso, Roberto Roberti and Marlin Ulmer

Transportation Research Part B: Methodological, 2025, vol. 192, issue C

Abstract: We consider a problem where customers dynamically request next-day home service, e.g., repair or installments. Unlike attended home delivery, customers cannot select a time window (TW), the service provider assigns a next-day TW to each new customer if the customer can feasibly be inserted in the service route of the next day without violating the TWs of the existing customers. Otherwise, customer service will be postponed to another day (which is outside the scope of this work). The provider aims to serve many customers the next day for fast service and efficient operations. Thus, TWs have to be assigned to keep the flexibility of the fleet for future requests. For such anticipatory assignments, we propose a stochastic lookahead method that samples a set of future request scenarios, solves the corresponding team-orienteering problems with TWs, and uses the solutions to evaluate current TW assignment decisions. For real-time solutions to the team orienteering problem, we propose to approximate its optimal solution value with an upper bound. The bound is obtained by solving the linear relaxation of a set packing reformulation via column generation. We test our algorithm on Iowa City data and compare it to several benchmark policies. The results show that our method significantly increases customer service, and our relaxation is essential for effective decisions. We further show that our policy does not lead to observable discrimination against inconveniently located customers.

Keywords: Next-day service; Dynamic time-window assignment; Stochastic lookahead; Approximate dynamic programming; Column generation (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261524002613
Full text for ScienceDirect subscribers only

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:eee:transb:v:192:y:2025:i:c:s0191261524002613

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2024.103137

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().