Vehicle Routing Problem for Multiple Product Types, Compartments, and Trips with Soft Time Windows
Site: | Saylor Academy |
Course: | BUS606: Operations and Supply Chain Management |
Book: | Vehicle Routing Problem for Multiple Product Types, Compartments, and Trips with Soft Time Windows |
Printed by: | Guest user |
Date: | Saturday, September 7, 2024, 7:58 PM |
Description
Read this article. The paper presents a mathematical model to solve vehicle routing challenges. In your own words, explain what vehicle routing is and why it's important to a supply chain.
Abstract
This paper presents a mathematical model to solve the vehicle routing problem with soft time windows (VRPSTW) and distribution of products with multiple categories. In addition, we include multiple compartments and trips. Each compartment is dedicated to a single type of product. Each vehicle is allowed to have more than one trip, as long as it corresponds to the maximum distance allowed in a workday. Numerical results show the effectiveness of our model.
Source: P. Kabcome and T. Mouktonglang, https://www.hindawi.com/journals/ijmms/2015/126754/ This work is licensed under a Creative Commons Attribution 3.0 License.
Introduction
The vehicle routing problem (VRP) is a well-known
problem in the operation research and combinatorial optimization
presented by Dantzig and Ramser. The VRP is also an important
problem in the fields of transportation, distribution, and logistics.
The context is planning the route to deliver goods from a central depot
to customers who have placed orders for such goods. The objective of the
VRP is to minimize the total route cost. According to the importance of
the VRP, there are so many literatures which refer to the models and
the solution of the VRP. Many papers present the different views of the
problem, the different features of the system, and the different
approaches to solve the problem.
The
vehicle routing problem with time windows (VRPTW) is a variant of the
VRP (Figure 1). A solution of the VRPTW is a set of routes consisting of
sequences of customers. Each route is assigned to arrive within their
time windows. In addition, if a vehicle arrives before (or after) the
lower (or upper) bound of the customer's time window, the vehicle cannot
deliver goods to the customer. An exception of VRPTW
problem is that the time windows can be violated if the penalty is paid.
In this case, it is called the vehicle routing problem with soft time
windows (VRPSTW). In VRPSTW, each customer has a desirable time
window with the highest satisfaction
as and a hard time window
. A soft
time window is shown in Figure 2. In the intervals
and
the service is allowed for some penalty fee.
Figure 1 Service time interval in VRPTW.
![](https://learn.saylor.org/pluginfile.php/5619138/mod_book/chapter/50034/126754.fig.001.png)
Figure 2 Service time interval in VRPSTW.
![](https://learn.saylor.org/pluginfile.php/5619138/mod_book/chapter/50034/126754.fig.002.png)
The
vehicle routing problem with multiple trips (VRPMT) is another variant
of the classical VRP. Each vehicle can be scheduled for more than one
trip, as long as it corresponds to the maximum distance allowed in the
workday.
The vehicle routing problem with multiple
compartments (VRPMC) is also a special case of the VRP. Each compartment
of the vehicle has a limit and is dedicated to a single type of
products.
Many papers present the different views of
VRP; there has not been any VRP mathematical model for multiple
compartments, trips, and time windows. Several papers presented VRP for
single product type. However, in "A mixed-binary linear model for fleet routing and multiple product-type distribution," the author presents a model on
distributing multiple items for customer.
In this paper, we
address the mathematical model for the VRP for multiple product types,
compartments, and trips with soft time windows (VRPMPCMTSTW). The
proposed VRP can be regarded as the extension to three problems which
are
(i) the vehicle routing problem with multiple compartments,
(ii) the vehicle routing problem with multiple trips,
(iii) the vehicle routing
problem with soft time windows.
The summary of the three
mentioned problems is presented in Table 1. It is clear that our
mathematical model solves the classical VRP since it is a special case
for the VRP with multiple compartments, trips, and time windows. The
time window cases are studied because they are more practical and the
soft time window cases are further investigated due to the feasibility
of the problem and, in some cases, due to the fact that it reduces the
total cost.
Table 1 Comparison of the problems.
VRP | VRPMC | VRPMT | VRPSTW | This study | |
Vehicle | Heter/homo | Single | Heter/homo | Heter/homo | Heter/homo |
Compartment | Single | Multiple | Single | Single | Multiple |
Trip | Single | Single | Multiple | Single | Multiple |
Time window | Not considered | Not considered | Not considered | Considered | Considered |
From the above content, model 3 generalizes all previous models mentioned in this paper. It is worth pointing out that another goal of the formulation is to try to formulate the mathematical models which are feasible and solvable by available solvers in a reasonable time. In this research, all models are solved by using AIMMS 3.13 on a personal computer. The remainder of the paper is organized as follows. In Section 2, the problem is defined. Also the assumptions, notations, and mathematical models are presented. Section 3 contains the computational results of our formulations. We use the same set of data from "A mixed-binary linear model for fleet routing and multiple product-type distribution," to examine the feasibility and solutions of the model. Finally, in Section 4, we summarize our conclusion and provide pointers for further research.
Problem Formulation
In this section, we present a mathematical
model for the vehicle routing problem for multiple product types,
compartments, and trips with soft time windows. The following notations
are introduced to formulate the mathematical model.
Sets (Indexes). Let be
a directed graph where
is a set of vertices and
is a set of arcs
representing the connections between the depot and customers and among
the customers, where
. Indeed, let
be a node set (o is origin and d is
destination),
be a set of compartments,
be a set of trips.
Parameters. Let
be
a distance between customers
and
,
be a time (hour) from customers
to
(e.g.,
when
means traveling speed of each vehicle),
be the demand of
the customer
in product
,
be the capacity of a compartment
in the
vehicle
,
be an arbitrary big number (e.g.,
),
be the fixed cost per
kilometer of running of each vehicle,
be the cost per unit travel per
unit of load of product type by the vehicle,
be a service time at the
customer
,
be the lower bound of soft time window for the node
,
be
the upper bound of soft time window for the node
,
be the lower bound
of hard time window for the node
,
be the upper bound of hard time
window for the node
,
be penalty cost per hour for the earliness,
be penalty cost per hour for the lateness.
Decision Variables. Consider
is the quantity of product type
to be transported from node
to node
by
vehicle
in trip
,
is the quantity of product type
to be disposed at
node
by vehicle
in trip
,
is the starting time of service in node
by
the vehicle
in trip
,
is the violation degree of a lower bound of soft
time window,
is the violation degree of an upper bound of soft time window, and
The problem is solved under the following assumptions:
(1) Every customer can be served by one and only one vehicle.(2) Every vehicle starts and ends only at the central depot.
(3) The total demand on one particular route must not exceed the capacity of the vehicle.
(4) Each customer must be served in the related hard time window.
(5) A service (wait) time in each customer is allowed.
(6) The hard time windows must not be violated.
(7) The soft time windows can be violated at a fixed cost.
Mathematical Model. The
vehicle routing problem for multiple product types, compartments, and
trips (model 1) can then be stated mathematically as follows:
We
minimize objective function (3) which consists of two components. The
first component represents traveling cost. It depends on distances
covered by vehicles and the fixed costs per unit distance. The second
component is defined as the fleet cost which is equal to the sum of the
costs related to the loading and distance. Constraints (4) are the flow
conservation of a vehicle. That is, for , every vehicle starts only once
at the depot and no arc terminates at node
, and also, for
, every
vehicle ends only once at the depot and no arc originates from node
,
and
indicate that exactly one vehicle enters and leaves each customer
node. Constraints (5) require the fact that each customer is serviced
exactly once. Constraints (6) state that all customers must be assigned
to at most one vehicle. Constraints (7) ensure that the total number of
quantity transported does not exceed the vehicle's capacity. Constraints
(8) state that the sum of the quantities of product type disposed at a
customer by all the vehicles must be equal to the demand for product
.
Constraints (9) represent the sum of quantities of the product type to
be transported by the vehicle to the customer from the depot node (o). It
should in total be greater than the total sum of the demands at all
customers. Constraints (10) state that the quantity of product
transported to a customer minus the quantity disposed at that customer
must be equal to the quantity transported to the next customer by the
vehicle. Constraints (11) represent the transported quantity. That is,
variable
if route segment
is not used by vehicle
; otherwise it should
not exceed the total tonnage capacity of vehicle
. Constraints (12)
state that each vehicle must not load at the depot. Constraints (13) and
(14) are the flow conservation constraints which describe the vehicle
path. Constraints (15) define a limit for each compartment to be
dedicated to a single type of product.
This model can be extended
to the model called vehicle routing problem for multiple product types,
compartments, and trips with time windows (model 2). In the next model,
we include the time windows for each node. Consider (16)
Constraints (16) ensure feasibility of the time schedule; that is,
must be greater
than or equal to \(\) whenever the vehicle
travels from
to
. By rewriting
constraints (16), they can be replaced with the following constraints:
Constraints (18) ensure that the starting time of a service does not violate the given hard time window.
Proposition 1. Constraints
are valid for model 2. Moreover, any that satisfies constraints (19) satisfies constraints (17).
Proof of Proposition 1 is straightforward and, thus, we omit it.
The vehicle routing problem for multiple product types, compartments, and trips with time windows can be stated as follows:
subject to: (4) - (15), (18), (19)
Constraints
(18) assure that the starting time of services does not violate the
given hard time windows. Constraints (21) assure that the starting time
in next trip of each vehicle is satisfied.
Finally we consider
the complete the generalization of all models mentioned in this paper.
We include soft time windows for each time window allowing the vehicle
to enter the depot earlier or later with some penalties. The vehicle
routing problem for multiple product types, compartments, and trips with
soft time windows (model 3) can then be stated mathematically as
subject to: (4) - (15) , (22),
The
objective function differs from models 1 and 2 by adding the third
component. The objective function is to minimize the sum of the cost of
traveled distances, total of costs related to loading products, and the
total penalties of the outrage from soft time windows. We then replaced
constraints (19) and (18) by constraints (23). Constraints (24)
determine the violation degree of the lower and upper bound of soft time
windows for each node.
Numerical Results
Let be nodes where
and
are the same nodes.
First of all, we consider test problems in order to observe the
feasibility and solvability of the models. We test our models on the
sets of 5, 10, and 15 customers. We use the same set of data
to examine the feasibility and solutions of the model. Clearly, our
models are more general. However, we use this data
set as a special case. Second of all, we randomly generate demands,
service times, time windows of the customers, and distances between
nodes as in Tables 2–6. The demands of customers are given in Tables
4–6.
Table 2 Distance from a node to a node
Table 3 The time windows for each node .
1 |
2 | 3 |
4 |
5 |
6 |
7 |
8 | 9 |
10 |
11 | 12 |
13 |
14 |
15 |
||
6 |
10 |
16 |
13 |
15 |
8 |
10 |
8 |
13 |
10 | 11 | 9 | 9 |
9 |
10 |
10 |
|
20 |
11 |
20 |
16 |
17 |
9 |
12 |
10 |
14 | 17 | 14 | 11 | 12 | 10 |
15 |
17 |
Table 4 The demand at the node for five customers.
1 |
2 | 3 |
4 |
5 |
||
0 |
100 |
200 |
200 |
300 |
50 |
|
0 |
100 |
100 |
70 |
30 |
20 |
Table 5 The demand at the node for ten customers.
1 |
2 | 3 |
4 |
5 |
6 |
7 |
8 | 9 |
10 |
||
0 |
50 |
100 |
120 |
40 |
30 |
60 |
80 |
50 |
130 |
40 | |
0 |
100 |
90 |
70 |
30 |
20 |
50 |
30 |
40 | 60 | 80 |
Table 6 The demand at the node for fifteen customers.
1 |
2 | 3 |
4 |
5 |
6 |
7 |
8 | 9 |
10 |
11 | 12 |
13 |
14 |
15 |
||
0 |
20 |
100 |
30 |
40 |
10 |
30 |
30 |
60 |
10 | 20 | 40 | 20 |
100 |
20 |
40 |
|
0 |
80 |
60 |
70 |
30 |
20 |
40 |
40 |
10 | 20 | 70 | 20 | 50 | 10 |
50 |
30 |
We assume that there are two vehicle types:
Table 7 The capacity for compartment of vehicle
.
200 |
200 |
100 |
|
300 |
300 |
200 |
Table 8 The fixed cost of travelling per k.m. and the capacity
of vehicle
.
10 |
6 |
|
500 |
800 |
Table 9 The cost of loading for product by each vehicle
.
10 |
6 |
|
4 |
8 |
All models have been coded and solved by AIMMS 3.13. They were run on a computer equipped with a processor Intel Core i5 at 2.3 GHz and 2 GB of RAM memory. The optimal solutions are obtained in Tables 10–12. The average run time for each case is included in Tables 10–12. As one can see, our model can be executed by an available solver on a personal computer in a reasonable time. We present the detailed optimal results of model 3 in the case of 15 customers for the effectiveness of the model. The optimal solutions are presented in Tables 13–16.
Table 10 The solution for five customers.
Model 1 | Model 2 | Model 3 | |
Objective value | 60346 | 61016 | 60476 |
Loading cost | 59860 | 60500 | 59860 |
Travel cost | 486 | 516 | 486 |
Penalty cost | — | — | 130 |
Vehicle 1 Trip 1 Trip 2 |
0 → 1 → d 0 → 5 → d |
0 → 5 → d 0 → 1 → d |
0 → 5 → d 0 → 1 → d |
Vehicle 2 Trip 1 Trip 2 |
0 → 3 → 2 → d 0 → 4 → d |
0 → 4 → 3 → d 0 → 2 → d |
0 → 4 → d 0 → 3 → 2 → d |
Times (seconds) |
0.37 | 0.27 |
0.5 |
Table 11 The solution for ten customers.
Model 1 | Model 2 | Model 3 | |
Objective value | 106574 | 110744 | 109130 |
Loading cost | 105620 | 109780 | 107840 |
Travel cost | 954 | 964 | 1010 |
Penalty cost | — | — | 280 |
Vehicle 1 Trip 1 Trip 2 |
0 → 5 → 10 → d 0 → 4 → d |
0 → 7 → d 0 → 1 → 6 → 8 → d |
0 → 6 → 7 → d 0 → 1→ 10 → d |
Vehicle 2 Trip 1 Trip 2 |
0 → 6 → 8 → 0 → d 0 → 1 → 2→ 3 → 7 → d |
0 → 5 → 9 → 10 → d 0 → 3 → 2 → 4 → d |
0 → 5 → 9 → 8 → d 0 → 3 → 2 → 4→ d |
Times (seconds) |
28 | 5 |
11 |
Table 12 The solution for fifteen customers.
Model 1 | Model 2 | Model 3 | |
Objective value | 74548 | 107098 | 83228 |
Loading cost | 73540 | 105900 | 81760 |
Travel cost | 1008 | 1198 | 1078 |
Penalty cost | — | — | 390 |
Vehicle 1 Trip 1 Trip 2 |
0 → 4 → 5 → d 0 → 12 → 3 → 10 → d |
0 → 5 → 7 → → d 0 → 1 → 6 → 3 → 14 → d |
0 → 5 → 12 → 11 → d 0 → 1→ 10 → d |
Vehicle 2 Trip 1 Trip 2 |
0 → 1 → 2 → 11 → 9→ d 0 → 13 → 14→ 15 → 7 → 6 → 8 → d |
0 → 13 → 12 → 11 → 10 → 9 → 8 → d 0 → 4 → 2 → 15 → d |
0 → 13 → 14 → 15 → 7 → 6 → 8 → 9 → d 0 → 3 → 2 → 4→ d |
Times (seconds) |
287 | 1320 |
1599 |
Table 13 The service time at node by a vehicle
in a trip
.
Vehicle 1 |
||||||||
Trip 1 | 5 → 7.75 |
12 → 8.5 |
11 → 9.2 |
d 10.4 |
|
|||
Trip 2 | 1 → 11.15 |
10 → 12.35 |
d 20 |
|||||
Vehicle 2 |
||||||||
Trip 1 | 13 → 9 |
14 → 9.55 |
15 → 10.2 |
7 → 10.8 |
6 → 11.45 |
8 → 12.5 |
9 → 13.3 |
d 14.6 |
Trip 2 | 3 → 15.6 |
2 → 16.3 |
4 → 17.15 |
d 20 |
Table 14 The violation degree of the bound for soft time at node .
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 | 9 |
10 |
11 | 12 |
13 |
14 |
15 |
|
Vehicle 1 |
|||||||||||||||
Trip 1 | 0.25 | 0.5 | |||||||||||||
Trip 2 | |||||||||||||||
Vehicle 2 |
|||||||||||||||
Trip 1 | 0.5 | 0.45 |
|||||||||||||
Trip 2 |
|||||||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 | 12 | 13 |
14 |
15 |
Vehicle 1 |
|||||||||||||||
Trip 1 |
|||||||||||||||
Trip 2 | 0.15 | ||||||||||||||
Vehicle 2 |
|||||||||||||||
Trip 1 | 0.8 | ||||||||||||||
Trip 2 | 0.15 |
Table 15 The load of the product in a compartment
of vehicle
.
Table 16 The quantity of product moved from node
to node
and delivered at node
for fifteen customers.
From the numerical examples, it is to be expected that the optimal values for the case where time windows are allowed are less than the case where the time windows are not allowed. Detailed results on each problem can be found in Tables 10, 11, and 12 for the of cases models 1 and 2. However, there are a few cases where the time windows do not have any effect. In these cases, the optimal values for both cases should be coincided. As for the case with soft time windows, together with the penalty, we expect that the optimal value of the soft time windows case should obviously be less than the (hard) time windows since the feasible solution set for the soft time windows is strictly larger than the feasible solution set or the time windows. The results of this experiment are shown in Tables 10, 11, and 12 in cases of models 2 and 3.
Conclusion
In this paper, we present a mathematical model for
the vehicle routing problem for multiple product types, compartments,
and trips with soft time windows. We have verified our feasibilities and
attended the optimal solution for the problems. We use the software
package AIMMS to solve the problems on a personal computer. The run
times are acceptable. Numerical results show the effectiveness of our
model.