Logic-based Benders decomposition for the HVRPTW

My implementation of the Logic-based Benders decomposition algorithm from the paper:

Fachini, R. F., & Armentano, V. A. (2020). Logic-based Benders decomposition for the heterogeneous fixed fleet vehicle routing problem with time windows. Computers & Industrial Engineering, 148, 106641.

Problem Description

The Heterogeneous Vehicle Routing Problem with Time Windows (HVRPTW) is a complex combinatorial optimization problem and an extension of the classic Vehicle Routing Problem (VRP). Unlike standard VRPs where all vehicles are identical, HVRPTW considers a diverse fleet of vehicles with different capacities and costs, while also adhering to specific delivery time windows.

The goal is to design a set of optimal routes to serve a specific group of customers such that total operational costs are minimized.

Key Components

• Heterogeneous Fleet: The fleet consists of different vehicle types. Each type may have different:
  • Capacity: Maximum load it can carry.
  • Fixed Cost: The cost of acquiring/using the vehicle.
  • Variable Cost: The cost per unit of distance traveled.
• Time Windows $[e_i, l_i]$: Each customer $i$ must be served within a specific time interval.
  • If a vehicle arrives too early, it must wait until the window opens.
  • Arriving after the window closes is strictly prohibited (Hard Time Window).
• Demand: Each customer has a specific quantity of goods to be delivered.

Constraints

1. Route Start/End: Every route must start and end at the central depot.
2. Single Visit: Each customer must be visited exactly once by exactly one vehicle.
3. Capacity Limit: The total demand of customers on a route cannot exceed the capacity of the assigned vehicle.
4. Time Feasibility: Vehicles must arrive at each location within the designated time window, accounting for travel time and service time.

Objective Function

The primary objective is typically to minimize the total cost, defined as:

$$\text{Total Cost} = \sum (\text{Fixed Vehicle Costs}) + \sum (\text{Variable Distance-based Costs})$$