A multiple asset-type, collaborative vehicle routing problem with proximal servicing of demands

Stephen D. Donnel, Brian J. Lunday and Nicholas T. Boardman

European Journal of Operational Research, 2025, vol. 321, issue 3, 974-990

Abstract: This research examines the problem of routing multiple assets of different types over a network to service demands in a collaborative manner. The servicing is collaborative in that, when servicing a demand, the different types of assets must do so nearly simultaneously. Moreover, whereas some asset types must service demands by visiting them, other asset types may provide service proximally. This study sets forth a mixed-integer linear program to model this variant of a vehicle routing problem. In addition to directly solving problem instances via a commercial solver, this research proposes two permutations of a model decomposition heuristic, as well as two preprocessing techniques to impose instance-specific bounds on selected decision variables. Comparative testing on mesh networks evaluates nine combinations of solution methods and preprocessing options to solve a set of 216 instances that vary significant parameters. Results manifest trade-offs between the likelihood of finding a feasible solution with bounded computational effort and the relative quality of solutions identified. For larger networks, the preprocessing technique leveraging a nearest neighbor heuristic in combination with any solution method most frequently identified feasible solutions for the set of test instances (i.e., ∼90% of instances), with lesser solution quality (i.e., within 15% of the best solutions identified, on average). Worst performing for larger networks was a model decomposition technique that first routes assets providing service proximally, and omitting either preprocessing technique; although this combination yielded the best solutions when it identified a feasible solution, it only did so for ∼55% of instances. Other solution method performances exhibit noteworthy nuance, as detailed herein. Further testing of the solution procedures on 216 additional instances for a scenario motivated by a disaster relief using a city road network yielded relatively consistent results; the superlative method leveraged model decomposition and a nearest neighbor preprocessing heuristic, albeit when routing proximally-serving assets first.

Keywords: Vehicle routing; Adjustable time windows; Proximal service; Model decomposition; Feasible region reduction (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724007628
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:321:y:2025:i:3:p:974-990

DOI: 10.1016/j.ejor.2024.10.009

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