Pro-active real-time routing in applications with multiple request patterns

Francesco Ferrucci and Stefan Bock ()

European Journal of Operational Research, 2016, vol. 253, issue 2, 356-371

Abstract: Recent research reveals that pro-active real-time routing approaches that use stochastic knowledge about future requests can significantly improve solution quality compared to approaches that simply integrate new requests upon arrival. Many of these approaches assume that request arrivals on different days follow an identical pattern. Thus, they define and apply a single profile of past request days to anticipate future request arrivals. In many real-world applications, however, different days may follow different patterns. Moreover, the pattern of the current day may not be known beforehand, and may need to be identified in real-time during the day. In such cases, applying approaches that use a single profile is not promising. In this paper, we propose a new pro-active real-time routing approach that applies multiple profiles. These profiles are generated by grouping together days with a similar pattern of request arrivals. For each combination of identified profiles, stochastic knowledge about future request arrivals is derived in an offline step. During the day, the approach repeatedly evaluates characteristics of request arrivals and selects a suitable combination of profiles. The performance of the new approach is evaluated in computational experiments in direct comparison with a previous approach that applies only a single profile. Computational results show that the proposed approach significantly outperforms the previous one. We analyze further potential for improvement by comparing the approach with an omniscient variant that knows the actual pattern in advance. Based on the results, managerial implications that allow for a practical application of the new approach are provided.

Keywords: Dynamic vehicle routing; Multiple request patterns; Request forecasting; Scenario identification; K-means clustering (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716300364
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:ejores:v:253:y:2016:i:2:p:356-371

DOI: 10.1016/j.ejor.2016.02.016

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().