An Integrated Heuristic Approach for the Long-Distance Heterogeneous Vehicle Routing Problem

Introduction

Logistics, managing the flow of products/services and information from points of origin to the points of consumption, has become an important functional area of companies due to the advantages it may induce. The benefits it brings are conceivably compelling and numerous including but not limited to a decrease in operational costs, reduction of inventories carried, a decline of time wasted as well as the betterment of storage and transportation of goods; all of these constitute in culminating customer service levels. Logistics management, a subdivision of supply chain management, is concerned with the optimal planning, control, and monitoring of the material/service and information flow both within and across partners of a supply chain.

Finding the optimal route plan for a fleet of vehicles is one of the most encountered problems in logistics in contemporary supply chains extending from private companies to governmental organizations. Better coordination of vehicle routing activity in these supply chains results in significantly decreased operational costs. Dubbed as the well-known vehicle routing problem (VRP), its applications encompass courier delivery services, bus services, mail services, patrol services, maintenance services, unmanned airborne vehicle services, among others. VRP, first introduced by Dantzig and Ramser (1959) as the truck dispatching problem, is a well-known NP-hard combinatorial optimization problem (Lenstra & Rinnooy Kan, 1981).

The VRP aims to find the optimal routes (i.e., minimum distance/time/cost) to be traveled by a fleet of vehicles to several destinations while satisfying the requirements of customers. Through time, the VRP has been extended and the variants now included several of the following constraints (i) load of a truck assigned to a route should not exceed the capacity of the truck; (ii) all routing activity should start and end at the same depot; (iii) deliveries should be made only by one truck in a route; (iv) deliveries should be made before pickups; (v) trucks don’t have to return to the depot after deliveries; (vi) a route can contain just delivery customers; (vii) no route should contain pickup customers only; (viii) trucks can visit any of the depots; (ix) total time for a route should not exceed an upper bound; and (x) a customer should be visited within a certain time; inter alia. Accordingly, the route planning is affected by truck capacities, customer demand quantities, number of depots, homogeneous-heterogeneous fleet types, the delivery time of products, delivery types including pickup and split loads, etc.

The solution time of the VRP increases exponentially in the size of the problem due to the NP-hardness. As a result, obtaining the exact solutions of VRP in a reasonable amount of time is impossible when the number of customers (i.e., retailers, stores) is exceeding 100 (Bettinelli, 2011). Thus, metaheuristic methods including genetic algorithm (Prins, 2004; Chang &Chen, 2007; Park et al., 2021), ant colony optimization (Bell & McMullen, 2004; Bin et al., 2009), tabu search heuristic algorithm (Gendreau, 1994; Taş et al., 2014) variable neighborhood search (Li et al., 2011; Taş et al., 2014), artificial bee colony algorithm (Iqbal, 2015), etc. were used to find near-optimal solutions. Yet, the exact algorithm such as the branch-and-cut-and-price algorithm (Bettinelli et al., 2011) was used to solve multi-depot heterogeneous VRP with time windows and was used to solve the robust capacitated VRP with knapsack uncertainty (Pessoa et al., 2021). Similarly, a branch-and-price algorithm was presented in Florio et al. (2021) to optimally solve VRP with random demands and stochastic interval constraints. Besides, approaches containing heuristic methods such as insertion heuristics (Solomon, 1987), column generation technique (Desrochers, 1992), etc. were successfully implemented to solve the VRP and its variants approximately. Recently, hybrid algorithms which combine two methodologies inclusive of neighborhood search and tabu search (Sicilia et al., 2016); artificial bee colony and local search for neighborhood selection (Iqbal et al., 2015); a ruin-recreate heuristic approach and a threshold tabu search (Wang et al., 2015); integrated ant colony and tabu search algorithm (Zhang et al., 2014), etc. have been proposed to solve the VRP and its variants in an efficient way. An early review paper on the VRP is Laporte (1992), a review of heuristic techniques is Vidal et al. (2013), and a recent review including a state-of-the-art classification on the topic is Braekers et al. (2016).