Title: Examining the effects of construction heuristics and problem structure on solution quality of the vehicle routing problem with split deliveries and time windows

Authors: Marcus McNabb; Jeffery Weir; Shane Hall

Addresses: Department of Operational Sciences, Air Force Institute of Technology, 2950 Hobson Way, Bldg 641, Room 201, Wright-Patterson AFB, OH 45433, USA ' Department of Operational Sciences, Air Force Institute of Technology, 2950 Hobson Way, Bldg 641, Room 201, Wright-Patterson AFB, OH 45433, USA ' Department of Operational Sciences, Air Force Institute of Technology, 2950 Hobson Way, Bldg 641, Room 201, Wright-Patterson AFB, OH 45433, USA

Abstract: This paper investigates the practical extension of the vehicle routing problem (VRP): the VRP with split deliveries and time windows (SDVRPTW). Although the SDVRPTW has not received much attention in literature, the papers hint that the underlying problem structure and ultimately methods required in generating high-quality solutions may differ significantly from the classical VRP. In particular, this paper uses a structured design of experiments to investigate the SDVRPTW, to include testing different construction heuristics, the effect of varying ratios of customer demand to vehicle capacity and the impact of splitting loads. Results indicate construction method does not substantively impact solution quality while local search operators with faster run times tend to generate higher-quality solutions where solution quality is primarily total distance travelled by the fleet of delivery vehicles.

Keywords: ant colony optimisation; construction; GRASP; heuristic; local search; split delivery; time windows; vehicle routing problem.

DOI: 10.1504/IJMHEUR.2017.085126

International Journal of Metaheuristics, 2017 Vol.6 No.3, pp.234 - 256

Accepted: 18 Nov 2016
Published online: 12 Jul 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article