Track: Logistics

Abstract

The increasing customer volume and limited resource capabilities (e.g., vehicle size, number of drivers, and trip duration) present substantial challenges in last-mile delivery operations. This research addresses these challenges by introducing an extension of the capacitated vehicle routing problem (CVRP) that allows multiple trips by each vehicle within a single workday and investigates the use of occasional drivers (ODs) as an alternative means to serve customers. This variant, called the capacitated multi-trip vehicle routing problem with time windows and occasional drivers (CMTVRPTWOD), aims to serve all customers within their predefined time windows while minimizing the total costs (i.e., delivery costs and compensation paid to ODs). The customers are serviced by a fleet of homogeneous company-owned vehicles and a set of ODs. Although the delivery company must pay compensation to the ODs it uses, this method could reduce delivery costs and increase profit, even if customer demand exceeds the capacity of the company’s vehicles for the day. The complexity of this extension is significantly increased by the multiple trips of vehicles and the compensation of ODs. We develop a mixed-integer programming (MIP) model for the problem and design a hybrid adaptive large neighborhood search (HALNS) algorithm for solving large-scale CMTVRPTWOD instances. Our proposed HALNS algorithm integrates the framework of adaptive large neighborhood search (ALNS) with variable neighborhood search (VNS). While small-sized instances can be solved by the MIP model using a commercial solver (i.e., CPLEX), large-sized instances can only be solved by the proposed HALNS. The benefits of the proposed model are apparent in the business context, especially for small and medium-sized enterprises.