A Heterogeneous Vehicle Routing Problem with Soft Time Windows for 3PL Company’s Deliveries: A Case Study

The classical VRP is one of the most important problems studied within the field of transportation optimization. This is due to the significant cost encountered in the transportation process. Since the problem has been introduced for the first time [1], it has been subject to numerous research. VRP, creates ideal delivery routes in which each vehicle only takes one route that starts from a centralized depot. The VRP's aim is to discover a set of least-cost vehicle routes in which each client is visited precisely once by one vehicle, each vehicle begins and ends its route at the depot, and the vehicle capacity is not overloaded [2-4]. The problem has been viewed and modeled from different perspectives and using several techniques, for example mathematical models [5], agent based VRP [6], and unified modeling language modeling [7]. The traditional VRP has been expanded in a variety of ways by including new real-life elements or traits, leading to a massive number of VRP variations. Extensions include changing the capacities of vehicles, resulting in the Heterogeneous Fleet VRP (HFVRP), also recognized as the Mixed Fleet VRP [8]. In VRP with time windows (VRPTW), which is another common extension, customers are often only available over a specific period. This adds up constraints on delivery/picking time, as the vehicle must visit a customer within a defined time frame [9, 10]. Failing to visit customers within their determined time window results in customer dissatisfaction. Another variant of the problem is the Vehicle routing Problem with Pickup and Delivery (VRPPD), in which each vehicle will pick up items/passengers at location A and drop them off at location B. On demand transport is a typical case – delivering services that satisfy consumer demands directly (e.g., taxi, shuttle service, buses, etc.). Routing results in paired pick-up and delivery points aligned with origin and destination. Goods must be picked up from a specific place and delivered to their destination. Because the pick-up and drop-off must be done by the same truck, the pick-up and drop-off locations must be included in the identical route. A similar issue is the VRP with backhauls (VRPB), in which a car does both deliveries and pick-ups along the same route. Some clients demand deliveries (known as line hauls), while others want pick-ups (referred to as backhauls). The combination of line hauls and backhauls has shown to be quite beneficial to the industry [1].

VRP with time windows could be categorized as VRP with hard time windows and VRP with soft time windows. In case of hard time windows, vehicles routing is done with the objective of minimizing total trip cost, and customers must be visited within their time windows without any flexibility in violating these time windows constraints. On the other hand, in VRP with soft time windows, the same objective holds, but visiting customers outside the predefined time windows of a customer is permitted at an additional cost known as penalty. The penalty is usually added to the trip cost and is proportional to the amount of time windows violation [11].

Heterogeneous vehicle routing problem with soft time windows (HVRPSTW) is an updated model from the VRP with soft time windows, where a set of customers are served using a fleet of heterogeneous vehicles. Vehicles with different capacities are located at a central depot, and are required to deliver customers’ demands. Customers’ coordinates and their associated demands are known before the start of the trip. Customers’ demands are assigned to vehicles, and hence vehicles depart to deliver demand to customers in a sequence that minimized the entire transportation costs of all customers’ deliveries, and at the same time, customers are to be visited as much as possible within their preset time windows. Time window violation is allowed at a cost. The time window violation cost is added to the transportation cost to be minimized [12]. After visiting the assigned customers, each vehicle ends the trip at the depot. VRP and its variants are NP hard in nature. Hence, only small size problems could be solved using exact methods to obtain optimal solutions [2]. Practical size problems require other solution methods like heuristics and metaheuristics. When adding time windows constraints and variability of truck types, VRP will be solved accurately with respect to the company’s given specific constraints and problem size. This will aid in saving costs by decreasing number of trips made and reducing time windows’ violation.

1.1 Related work

The authors [13] discuss a heterogeneous fleet VRP modeled by including the entire trip load constraint into the goal function. The problem is solved using a sequential inclusion heuristic with a punishment function that allows capacity breaches but limits them to a changeable specified upper bound. Periodic Heterogeneous Vehicle Routing Problem (PHVRP) is introduced in the reference [14]. The paper aim is to schedule deliveries based on viable combinations of delivery days, as well as to set fleet and driver scheduling and vehicle routing regulations. The authors [15] illustrate a Construction of a variety of velocity profiles along road segments, which are subsequently translated into traveling-time tables. A case study of rice distribution across communities by the bureau of logistics is presented to find the best option in terms of vehicle routes and service start times.

Column generation is used to solve the LP relaxation of the VRPTW’s set partitioning formulation [16]. An iterative route construction procedure is introduced in the reference [17] to solve the VRP with soft time windows as well as VRP with hard time windows. The proposed solution algorithm has quality and computing time that are comparable to existing solutions on benchmark problems. VRP with time windows in cross docking stations is presented in, and the problem in solved using Tabu Search and Variable Neighborhood Search methods [2, 18]. VRP with hard time windows and stochastic service times is formulated as a set partitioning problem and is solved using precise branch-cut-and-price algorithms [19]. The algorithm depends on creating efficient labelling algorithms by selecting appropriate label components and establishing lower and higher bounds on partial route decreased cost to be utilized in the column production phase. A case study considering distribution of liquefied petroleum gas in Turkey is discussed by Onut et al. [20], where the paper presents a model of heterogeneous vehicles used to deliver goods such that the total demand cannot exceed the vehicle capacity and the model was solved using GAMS for optimum solutions. Most studies in the field of VRP and its extensions focus on modelling the problem variants and/or developing heuristics or metaheuristics methods to solve large size problems. However, few research work addressed the variant of soft time windows. Moreover, and to the best of our knowledge, no research has addressed the topic of heterogeneous vehicle routing problem with soft time windows within the assumptions and constraints given in this work.

In this paper, a heterogeneous vehicle routing problem with soft time windows (HVRPSTW) is modeled to represent an existing case study in Egypt, as case studies are good for describing, comparing, evaluating and understanding different aspects of a research problem, and allows in-depth, multi-faceted explorations of complex issues in real-life settings. To the best of our knowledge, the developed model with the details representing the case study is a novel mixed integer linear programming mathematical model. To offer a solution to the company of the case study, the developed model is solved to optimality using LINGO software.

The rest of this paper is organized as follows: Section 2 provides a detailed description of the problem statement representing the case study, Section 3 illustrates the methodology adopted to solve the problem in hand, in Section 4 results obtained for the data of the case study are presented and, finally, Section 5 concludes the paper.

In this paper, the problem is mathematically formulated. The developed mathematical model is solved using LINGO software to obtain an optimum solution.

3.1 Mathematical formulation

A mixed integer linear programming model for the HVRPTW problem of the case study is formulated and given below.

The parameters used in the mathematical formulation are:

N: Number of nodes.

K: Maximum number of vehicles to employ.

Q_k: Capacity of vehicle type k.

$C_{i j}$: Transportation cost between node i and node j, where node 0 represents the site of the depot; i, j = 0, 1, 2… N and $C_{i j}$=0.

$P E_{-} C_{i}$: Early penalty cost for customer i, if vehicle arrives before the earliest allowed start time at node i, the service will start with considering this penalty cost; i= 1, 2... N and $P E_{-} C_{0}$= 0 where 0 is a central depot.

$P L_{-} C_{i}$: Late penalty cost for customer i, if vehicle arrives after the latest allowed start time at node i, the service will start with considering this penalty cost; i= 1, 2... N and $P L_{-} C_{0}=$= 0 where 0 is a central depot.

$T_{i j}$: Travel time between node i and node j, i, j = 0, 1, 2… N and $T_{i i}$ = 0.

$E_{j}$: Earliest allowed start time of service for the customer at node, j = 1, 2…N.

$L_{j}$: Latest allowed start time of service for the customer at node, j = 1, 2…N.

$S r_{j}$: Service time for the customer at node, j = 1, 2…N.

$d_{j}$: Amount of products to deliver to the customer at node j, j = 1, 2….N.

M: large positive number.

Decision Variables:

$x_{i j k}\left\{\begin{array}{c}1 \text { if vehicle } \mathrm{k} \text { travels from node } \mathrm{i} \text { to } \\ \mathrm{j} \mathrm{i}, \mathrm{j}=0 \ldots \ldots, N \\ 0 \quad \text { otherwise }\end{array}\right.$

$P E_{-} T_{j k}\left\{\begin{array}{c}1, \text { if service start time for customer } \\ \mathrm{j}, S t_{j}<E_{j}, j=1, \ldots, N \\ 0 \quad \text { otherwise }\end{array}\right.$

$P L_{-} T_{j k}\left\{\begin{array}{c}1, \text { if service start time for customer } \\ \mathrm{j}, S t_{j}>L_{j}, j=1, \ldots, N \\ 0 \quad \text { otherwise }\end{array}\right.$

$S t_{j}$: start of service time at customer j, j = 1,…,N.

$l d_{k}$: load of vehicle k at the start of the trip.

Objective Function:

The model's objective function is to minimize the total transportation costs, including penalties for arriving earlier or later than the time windows. The objective function is:

Min $=\sum_{i=0}^{N} \sum_{j=0}^{N} \sum_{k=1}^{K} C_{i j k} X_{i j k}+$

$\sum_{j=1}^{N} \sum_{\mathrm{k}=1}^{K} P E_{-} C_{j} * P E_{-} T_{j k}+\sum_{\mathrm{j}=1}^{N} \sum_{\mathrm{k}=1}^{K} P L_{-} C_{j} *$

$P L_{-} T_{j k}$                 (1)

Constraints:

The objective function is subject to the following constraints:

$\sum_{i=0}^{N} \sum_{k=1}^{K} X_{i j k}=1 \quad j=1, \ldots, N$            (2)

$l d_{k}=\sum_{i=0}^{N} \sum_{i=1}^{N} d_{j} X_{i j k} \forall k \in K$        (3)

$l d_{k} \leq Q_{k} \quad \forall \mathrm{k} \in \mathrm{K}$           (4)

$\sum_{i=0}^{N} \mathrm{x}_{\mathrm{ibk}}-\sum_{j=0}^{N} \mathrm{x}_{\mathrm{bjk}}=0 \quad b=1, \ldots N, \forall \mathrm{k} \in \mathrm{K}$         (5)

$M \times P E_{-} T_{j k}+S t_{j} \geq E_{j}$      (6)

$-M \times\left(1-P E_{T_{j k}}\right)+S t_{j}<E_{j}$       (7)

$-M \times P L_{-} T_{j k}+S t_{j} \leq L_{j}$         (8)

$M \times\left(1-P L_{T_{j k}}\right)+S t_{j}>L_{j}$

$j=2 \ldots \ldots N, k=1,2 \ldots \ldots . K$         (9)

$S t_{i}+T_{i j}+S r_{i}-M \times\left[1-x_{i j k}\right] \leq S t_{j}$

$i=0 \ldots N, j=2 \ldots N, k=1 \ldots K$          (10)

$X_{i j k}=\{0,1\} i, j=1, \ldots \ldots N, k=1,2 \ldots \ldots . K$        (11)

$P E_{-} T_{j k}=\{0,1\} j=2, \ldots \ldots N, k=1,2 \ldots \ldots . K$        (12)

$P L_{-} T_{j k}=\{0,1\} j=2, \ldots \ldots N, k=1,2 \ldots \ldots . . K$       (13)

Constraint (2) assures that vehicle k visits node j from node i only once. In constraint (3), the load of a vehicle is calculated according to the demand for all nodes j assigned to the vehicle. Constraint (4) assures that the total load assigned to a vehicle does not exceed the vehicle’s capacity. Constraint (5) states that when a vehicle visits a node will ultimately leave it (flow conservation constraint). Constraints (6) and (7) determine whether the vehicle visits a node earlier than the earliest allowable time of the time window, and accordingly, determines the amount of violation and the penalty for early arrival, if exists. Constraints (8) and (9) determine whether the vehicle visits a node later than the latest allowable time of the time window, and accordingly, determines the amount of violation and the penalty for late arrival, if exists. Constraint (10) calculates the start of service time, which equals to the arrival time, at customers’ nodes. Constraints (11) to (13) are binary constraints.

3.2 ABC company’s cost structure

Table 1. Oil changes

A cost structure was prepared to set a pricing criterion for the contractors. The cost structure depends on the influencing factors that affect the costs of a trip, directly and indirectly and on the short and long term such as the running costs (oil /3000 Km, diesel consumption/ liter 100 Km, loaded vehicle diesel consumption, tires and the deteriorated engine consumption (it is calculated based on each 800 Km) for the two types of trucks used in ABC Company (N series (6 tires) and T series (4 tires) as shown in the Tables 1-5. After calculating the overall cost which includes diesel price / liter/100 Km, it will be used in the mathematical formulation to minimize the trip cost.

Table 2. Diesel consumption

Table 3. Loaded diesel consumption

Table 4. Tires

Table 5. Deteriorated engine consumption

3.3 Software implementation

To test the effectiveness of the model, it is using a linear programming software. This study applies the model on LINGO software, the following data is gathered and assembled on ABC Company’s routing problem. Some of the data is collected by calculating the time and the destination using Google Maps. It represents a limited form of the data to test the efficiency of the model. ABC Company requires a centered depot among the nodes to be reachable by every destination. They deal with the following locations:

• Node1: Ezz Al Arab Agouza location
• Node 2: Mall of Arabia location
• Node 3: Dandy Mall location
• Node 4: Cairo festival city (CFC) location
• Node 5: Mall of Egypt location
• Node 6: City Center Almaza location

The six locations mentioned are represented by nodes from 1 to 6, respectively. The first node (depot) has a capacity of 100 units and the system operates with two vehicles with capacities of 50 and 80 units. The cost/km according to the cost structure is 3.16 L.E. The rest of the data such as: demand, early and late hours, service time, travel time, and early/late penalty cost are represented in Tables 6, 7 in the form of nodes and matrices that satisfy these nodes. Data in Tables 8, 9 are extracted from a web mapping platform between each node.

HVRPSTW model requires these data in order to operate vehicles with different capacities to fully optimize vehicles, depot capacity that vehicles must meet, time window range to check the arrival time to each node, and finally penalty cost which is applied to both late and early arrivals.

Table 6. Demand units, early & late minutes, and service time at each node

Table 7. Randomly generated numbers for penalties

 Table 8. Distance between defined nodes in Km

Table 9. Travel Time in minutes between nodes