Project topics and materials
Get Complete Project Material File(s) Now! »
Multi-Compartment VRP and its applications
In this section, we provide an overview of the works on Multi-Compartment VRP. We first describe the problem and its characteristics related to multiple commodities (see Section 2.2.1). Then, the main related applications are reviewed: petroleum products transportation (Section 2.2.2), waste collection (Section 2.2.3), livestock collection (Section 2.2.4), and food transportation (Section 2.2.5).
Multi-Compartment VRP
In the Multi-Compartment VRP (MCVRP), according to the general definition pro-posed by Derigs et al. (2011), each vehicle is divided in the same set of compartments each with a limited capacity and each customer requires a set of commodities. Two dimensions of incompatibilities are considered. First, some pairs of commodities are incompatible and must not be transported in the same compartment. Second, some commodities must not be loaded into some compartments. Each customer may be visited by several vehicles, but each required commodity has to be delivered at once by a single vehicle. In term of assignment decisions, the MCVRP requires to deter-mine, for each customer, in which compartment goes each required commodity. The result is a more complex problem than the classical CVRP where decisions simply involve the assignment of customers to vehicles. The MCVRP imposes additional constraints specifically related to the compartments: (i) the capacity of a compart-ment has to be respected, (ii) incompatible commodities cannot be assigned to the same compartment, (iii) each commodity is assigned to a compatible compartment.
Hence the main change from the classical CVRP is in the structure of the vehicles that are adapted to be able to transport several incompatible commodities. When all commodities are incompatible with each other, the routing problem is usually decomposed, which results in a higher routing cost. Using specific vehicles with multiple compartments is a way to decrease the routing costs when commodities are incompatible.
We still refer to the example shown in Figure 2.1, and we assume that each vehicle has 2 compartments with 5 units of capacity for each commodity. Figure 2.5 shows the solution to this instance, the total cost is 31. Obviously, this cost is lower than the case of separate routing (Figure 2.4), but greater than the SDVRP variant (Figure 2.3) where all commodities are compatible, and the deliveries can be split.
Petroleum distribution
The petroleum products/fuel distribution problem is known as the petrol station replenishment problem (Cornillier et al., 2008a). It is the most widely studied ap-plication of the MCVRP. The objective is to minimize the transportation costs for the distribution of several fuel products to a set of fuel stations (customers), using vehicles with multiple compartments since the fuel products cannot be mixed in the same compartment. Hence, each fuel product represents a commodity. Since accidental mixing of fuel products can be hazardous, compartments are not flexible and well separated from each other (Chajakis & Guignard, 2003). According to Cornillier et al. (2008a), compartments are usually not equipped with debit meters, which implies that when a delivery is made from a compartment to a tank in the fuel station, all the quantity loaded in the compartment has to be delivered. Hence, each compartment is dedicated to a single customer and a single commodity. Several compartments can be used to deliver a single commodity. In this application, all the commodities required by a customer have to be delivered at once by a single vehicle. Note that in practice a vehicle contains from 3 to 6 compartments and stations require from 2 to 3 fuel products, hence the number of stations visited on a given route rarely exceed 2 (Cornillier et al., 2008a). Moreover, the quantity of a fuel product delivered to a station is a decision variable. It has to be sufficient to cover the demand for this product, but cannot exceed the capacity of the tank in the station.
The introduction of the petroleum products distribution can be credited to Brown & Graves (1981). They studied a special case with time windows for the delivery considering only direct trips to the stations. Later, more and more re-searchers began to pay attention to the petroleum products distribution problems. Avella et al. (2004) study a particular case where the vehicle compartments can-not be partially filled: they have be either completely filled or empty. The authors propose a fast heuristic and a branch-and-price algorithm to solve the problem. Cornillier et al. (2008a) propose an exact algorithm to solve the problem by decom-posing the routing problem and the vehicle loading problem. The routing problem takes advantage of the fact that routes are usually short and can be enumerated. The vehicle loading problem is formulated as a MIP, and the authors propose an optimal algorithm to solve the problem. Cornillier et al. (2009) study an extension of the problem where stations have to be delivered within specified time windows. In that case, a vehicle can perform several trips during the one-day planning horizon. The authors propose two heuristics to solve the problem.
The petroleum products are usually delivered over a planning horizon of several days. Hence they integrate inventory management for the tanks in the stations. Cornillier et al. (2008b) propose a MIP model and a heuristic to solve the problem in the multi-period case. In this case, the objective is to maximize the total profit. Cornillier et al. (2012) address the multi-depot version, and they propose a heuristic based on the generation of feasible pairs of routes and vehicles.
Surjandari et al. (2011) study a particular case faced by the national petroleum company in Indonesia. A set of 208 petrol stations require two fuel products within a given time window. A fleet of 76 heterogeneous vehicles are located in two depots and have to deliver the stations over a horizon of one day. A vehicle can perform several trips. In this work, it is allowed to split the delivery for a station, but not for a given commodity. The authors proposed a tabu search algorithm to solve the problem. Christiansen et al. (2015) study a real-world application in Greece for an oil company where commodities are different types of fuel. The customers are ships that are supplied with fuel by a fleet of specialized fuel supply vessels. The vessels have fixed compartments where the fuels are loaded. Each vessel can perform several trips during the planning horizon. Each trip starts by refilling the compartments with fuel. In a given trip, a compartment contains only one type of fuel, but in the next trip the type of fuel loaded in this compartment may change. Different compartments can contain the same type of fuel. Moreover, if different ships require the same fuel type, a single compartment can be used to deliver them. The authors propose a MIP formulation for the problem.
Multi-Commodity Pickup and Delivery TSP
The Pickup and Delivery Traveling Salesman Problem (PDTSP), also known as the one-commodity PDTSP, introduced by Hernández-Pérez & Salazar-González (2004), is a generalization of the classical TSP where the customers are divided into two groups: delivery customers that require a given amount of a commodity, and pickup customers that provide a given amount of this same commodity. A single vehicle with a fixed capacity has to perform a single tour to visit all the customers, starting and ending at the depot. The initial load of the vehicle can take any value between 0 and the capacity. The visit of a delivery customer decreases the load of the vehicle while the visit of a pickup customer increases the load. The objective of the PDTSP is to design a minimum cost Hamiltonian route such that the load of the vehicle is always feasible (between 0 and the capacity). It is assumed that a single commodity that has to be transported from pickup points to delivery points without pairing these points. Note that, according to the classification of pickup and delivery problems (Battarra et al., 2014), this definition corresponds to the many-to-many problems where a single commodity has multiple origins and destinations. For an extensive review of the pickup and delivery problems, the interested reader is referred to the survey by Berbeglia et al. (2007).
In the Multi-Commodity Pickup and Delivery Traveling Salesman Problem (m-PDTSP), a set of different commodities are transported by a single capacitated vehicle. Each customer requires and/or provides a given quantity of one or several commodities and must be visited once by the vehicle. All the commodities are compatible and can be mixed in the vehicle. The initial quantity of each commodity in the vehicle is a decision variable. The m-PDTSP aims to determine a Hamiltonian circuit such that all pickup and delivery requirements are satisfied and the vehicle capacity is not exceeded. The objective is to minimize the total transportation cost. In this problem, it is important to explicitly consider the different commodities since we have to ensure that there is sufficient amount of each required commodity in the vehicle when a customer is delivered.
Table of contents :
Acknowledgements
Table of Contents
List of Figures
List of Tables
1 Introduction
2 Vehicle routing with multiple commodities: a survey
2.1 Introduction
2.2 Multi-Compartment VRP and its applications
2.2.1 Multi-Compartment VRP
2.2.2 Petroleum distribution
2.2.3 Waste collection
2.2.4 Livestock collection
2.2.5 Food transportation
2.3 Multi-Commodity VRP extensions
2.3.1 Multi-Commodity Pickup and Delivery TSP
2.3.2 Traveling Purchaser Problem
2.3.3 Commodity constrained Split Delivery VRP
2.3.4 Multi-Commodity Inventory Routing Problem
2.3.5 Multi-Commodity Multi-Trip VRP
2.3.6 Multi-Commodity Location Routing Problem
2.4 Other applications with multiple commodities
2.4.1 Transportation of multiple hazardous materials
2.4.2 Transportation of multiple commodities in disaster relief
2.5 Conclusions and directions for further research
3 Adaptive Large Neighborhood Search for the Commodity constrained Split Delivery VRP
3.1 Introduction
3.2 Problem definition
3.3 Adaptive Large Neighborhood Search
3.3.1 General framework
3.3.2 Initial solution
3.3.3 Local search
3.3.4 Removal heuristics
3.3.5 Insertion heuristics
3.3.6 Acceptance and stopping criterion
3.3.7 Mathematical Programming based Operator to reassign commodities
3.3.8 Adaptive weight adjustment
3.3.9 Infeasibility penalization scheme
3.4 Computational experiments
3.4.1 Instances
3.4.2 ALNS parameters
3.4.3 Efficiency assessment for the removal and insertion heuristics .
3.4.4 Analysis with respect to the number of iterations
3.4.5 Computational experiments on the whole testbed
3.4.6 Effectiveness of MPO operator in the ALNS algorithm
3.4.7 Evaluation of the LS in the ALNS algorithm
3.4.8 Trend between instance size and computational time
3.4.9 Characteristics of split customers
3.5 Conclusions
4 A decomposition approach to a Multi-Commodity two-echelon Distribution Problem
4.1 Problem definition
4.2 A decomposition approach
4.2.1 The Collection Subproblem (SPC)
4.2.2 The Delivery Subproblem (SPD)
4.3 Analysis of the MC2DP
4.3.1 On the benefit of distribution centers
4.3.2 Sequential solution of the MC2DP
4.3.3 Complexity of special cases of the MC2DP
4.4 Solution approach
4.4.1 Solution of the SPC
4.4.2 Solution of the SPD
4.4.2.1 Initial solution
4.4.2.2 The Adaptive Large Neighborhood Search
4.4.3 Sequential solution approaches
4.4.3.1 Sequential solution: SPD → SPC
4.4.3.2 Sequential solution: SPC → SPD
4.5 Computational experiments
4.5.1 Instances
4.5.1.1 Generation of the base set of instances S
4.5.1.2 Modification of the supplier locations
4.5.1.3 Modification of the customer locations
4.5.1.4 Modification of the available quantities at suppliers .
4.5.1.5 Modification of the number of distribution centers
4.5.2 Comparison of the sequential approaches to solve the MC2DP
4.6 A case study
4.6.1 Context
4.6.2 Description of the data sets
4.6.3 Analysis of the results
4.7 Conclusion and future research
5 An integrated optimization approach for a Multi-Commodity twoechelon Distribution Problem
5.1 Introduction
5.2 Problem definition
5.2.1 The Multi-Commodity two-echelon Distribution Problem
5.2.2 Subproblems
5.2.2.1 The Collection Subproblem (SPC)
5.2.2.2 The Delivery Subproblem (SPD)
5.3 An integrated optimization algorithm
5.3.1 General framework
5.3.2 Initial solution
5.3.3 Large operators
5.3.3.1 A MIP formulation for the SPC
5.3.3.2 The operators for the SPC
5.3.3.3 The heuristic flow operator
5.3.4 Destroy and repair heuristics
5.3.5 Intensification procedure for the MC2DP
5.3.5.1 Local search to improve the SPD
5.3.5.2 Large moves to improve the MC2DP
5.4 Experimental results
5.4.1 Instances
5.4.2 Sequential strategies for the initial solution
5.4.3 Evaluation of the proposed algorithm
5.4.4 Analysis of the large operators
5.5 Conclusions and future works
6 Conclusions and perspectives
References
