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

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.