Vehicle Routing Problem for Multiple Product Types, Compartments, and Trips with Soft Time Windows
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.
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.