Vehicle routing for connected service areas - a versatile approach covering single, hierarchical, and bi-criteria objectives

Stefan Bock

European Journal of Operational Research, 2024, vol. 313, issue 3, 905-925

Abstract: Vehicle routing in urban areas or in-house tour planning is characterized by the fact that tours have to service orders in areas with limited road or aisle access. During last mile delivery, courier service providers often face the situation that subsets of customers in urban areas are located along a single street that can be accessed from only one or two directions. This also applies to warehouses, where, due to the given grid layout, pickers locate products on shelves only in specific areas positioned along an aisle between two neighboring cross aisles. By being confronted with a substantial time and/or cost pressure, those tour planning applications have to deal with the trade-off between service orientation and cost minimization. In order to cover many of those applications, this study proposes a general model that integrates the definition of customizable service areas with limited access and soft due dates of urgent orders, whereas the objective function can be defined in a versatile way covering to choose between a single objective, a hierarchical, and a bi-criteria objective system. The model is dubbed the Vehicle Routing Problem of Service Areas (VRPSA). A comprehensive complexity analysis of the VRPSA for different objective systems shows that a pure travel cost minimization variant can be solved to optimality in polynomial time, whereas the bi-criteria variant simultaneously pursuing travel cost and tardiness cost minimization is proven to be intractable. In order to generate tour plans, a customizable best-first branch-and-bound algorithm is developed and assessed through a computational study.

Keywords: Scheduling; Vehicle routing of service areas; Versatile objectives; Complexity analysis; Branch-and-bound (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172300680X
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:313:y:2024:i:3:p:905-925

DOI: 10.1016/j.ejor.2023.08.051

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 ().