BUS606: Operations and Supply Chain Management

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 $i$ has a desirable time window with the highest satisfaction $[a_i, b_i]$ as and a hard time window $[LB_i, UB_i]$. A soft time window is shown in Figure 2. In the intervals  $[LB_i, a_i]$ and $[b_i, UB_i]$ the service is allowed for some penalty fee.

Figure 1 Service time interval in VRPTW.

Figure 2 Service time interval in VRPSTW.

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.