Genetic Algorithm for Solving Multi-period and Multi-depot Vehicle Routing Problem with Time Window

Get Complete Project Material File(s) Now! »

Classification of Vehicle Routing Problem

In this section, the main characteristics and constituent elements of VRP are presented. On this basis, we introduce the different variants of VRP.

Constituent Elements of Vehicle Routing Problem

A typical VRP includes the below elements: road network, customer, depot, vehi-cle, side constraint and operational objective. An introduction to each constituent is given below.
The road network is the basis of the carriage of goods, which is one of the most important elements of VRP. A road network is usually represented by a weighted graph consisting of vertexes and arcs. The vertex represents the depot or the customer, and the arc represents the road connection between the customer and the depot or the customer. According to the different characteristics of the road connecting two points in the transport network, the arc can be divided into directed arc and undirected arc. The directional arc refers to the road where the vehicle can only travel in one direction, and a typical example is the one-way road in the urban transport network. The undirected arc refers to the two-way road where the vehicle can travel in both directions. Each arc can be given a non-negative cost weight. According to the actual needs of the study, it can be given different meanings. For example, it can represent the travel distance or the travel time and so on. The customer can represent any type of service object in the actual VRP, and its typical characteristic attributes include the following aspects:
– Customer corresponds to a vertex in the road network diagram.
– The customer point has a service demand, which can be the amount of goods delivered from the depot to the customer, or the amount of goods that need to be collected from the customer to the depot.
– Customer service time. It indicates the unloading time or cargo collection time of the customer.
– Customer service time window or time period. Some certain types of cus-tomers may have a service time window, which refers to the time interval during which the vehicle can start service to the customer, including the earliest allowed service time and the latest allowed service time.
The depot is the starting point or end point of each vehicle route. The vehicles deliver goods from the depot to the customer or collect goods from the customer to the depot. The depot is stationed with a group of vehicles to complete the delivery or collection service to the customers. In the general literature, VRP is assumed to have only one depot.
A group of vehicles complete the distribution or collection of goods for customers in VRP. The typical features include the following aspects:
– Type.
– Loading capacity.
– Cost. The vehicle cost here mainly refers to the fixed cost for use of the vehicle fixed costs and the variable cost. The variable cost refers to the cost for per kilometer or per hour.
– Duration. The vehicle used for goods delivery or collection has a maximum allowable travel distance or time. In the actual problem it indicates the maximum daily working hours of the vehicle driver.

VRP Extended Criteria

The previous chapter has given definitions and mathematical models of stan-dard VRP. The standard VRP is the simplest and most popular type of VRP in the field of operations research. Compared with standard VRP, VRP in the actual production operation management has new attributes and characteristics, such as service time window, undetermined quantity of demand, undetermined quantity of travel time and so on. The model and framework of standard VRP obviously cannot be used to model and analyze the new VRP. In order to meet the actual needs of production management, operational research studies the new VRP extensions by relaxing the assumptions of standard VRP and introducing new constraints to the standard VRP. These new expansion problems gradually broaden the breadth and depth of study for VRP.
We have two ways to relax standard VRP according to the constitutive ele-ments of VRP:
• By relaxing the assumptions of the standard VRP to generate new extended problems;
• By introducing new side constraints and integrating new service elements in the standard VRP based on the actual needs of production management.
The new VRP will gradually adapt to the actual needs of production management. Combining these extended elements with the standard VRP can build different types of VRP. The extended criteria are shown below.

Multi-Period Vehicle Routing Problem

In classical VRPs, typically the planning period is a single day. VRP of multi-period considers a planning horizon consisted of many period. In this way, the vehicles should execute many tours in the plan. There are two main types of MPVEP: the Periodic Vehicle Routing Problem (PVRP) and the Inventory Rout-ing Problem (IRP). In the PVRP, each customer may be served more than once. The objective is to minimize the cost while serve all customers for a certain num-ber of times. IRP has become a spot of research during last decades. It is a more global approach than the PVRP. It integrates inventory management, vehicle routing and delivery scheduling decisions (Coelho et al., 2013).
Prodhon (2008) combines the Location-Routing Problem (LRP) and PVRP into the Periodic LRP and proposed a metaheuristic based on Randomized Ex-tended Clarke and Wright Algorithm and tried to take into consideration several decision levels when making a choice during the construction of a solution. Alonso et al. (2008) and Prodhon (2011) both choose tabu search for PVRP. Exact al-gorithms are often used for multi-period VRP in the literature. Mourgaya & Vanderbeck (2007) use a truncated column generation procedure followed by a rounding heuristic to find approximate solutions. This method can only deal with problems with 50-80 customers over five working days. Dayarian et al. (2015) pro-posed a mathematical model based on a two-stage a priori optimization paradigm. The first stage is solved by a branch-and-price approach and the subproblem is solved by a dynamic programming based label-correcting algorithm. The PVRP is reviewed in Francis et al. (2008). Exact methods Baldacci et al. (2011) are able to solve some instances with up to 100 customers and 6 time periods. Sev-eral efficient neighborhood-centered searches have been designed Cordeau et al. (2001) and Cordeau & Maischberger (2012). The population-based approach of Alegre et al. (2007) dedicated to large temporal horizons, focuses on assignment optimization, while using constructive methods to create routes.

Table of contents :

1 Introduction
1.1 Motivation
1.2 Vehicle Routing Problem
1.3 Presentation of Problem Studied
1.4 Contributions of the Dissertation
1.5 Organization of the Dissertation
2 State of the Art 
2.1 Classification of Vehicle Routing Problem
2.1.1 Constituent Elements of Vehicle Routing Problem
2.1.2 VRP Extended Criteria
2.1.3 Vehicle Routing Problem Extensions
2.2 Solution Methodologies
2.2.1 Exact Algorithms
2.2.2 Heuristics
2.2.3 Meta-heuristics
2.3 Similar Variants to Our Problem
2.3.1 Multi-Period Vehicle Routing Problem
2.3.2 Multi-Depot Vehicle Routing Problem
2.3.3 Vehicle Routing Problem with Time Window
2.4 Conclusion
3 Heuristics of Construction and Improvement 
3.1 Problem Formalization
3.1.1 Problem Description
3.1.2 Constraints on Demands
3.1.3 Constraints on Vehicles and Periods
3.2 Mathematical Model
3.3 Heuristic of Construction
3.3.1 Adapt to Compatibility Between Requests and Period
3.3.2 Adapt to Priority of Customers
3.3.3 Algorithm for Construction
3.4 Heuristic for Improvement
3.4.1 Local Search Heuristic
3.4.1.1 Intra-route improvement
3.4.1.2 Inter-routes improvement
3.4.2 Local Search Heuristics for MDMPVRPTW
3.5 Experiment Results
3.5.1 Experimental Data
3.5.2 Results of Cplex
3.5.3 Results of Construction Heuristics
3.5.4 Results of Improvement Heuristics
3.6 Conclusion
4 Genetic Algorithm for Solving Multi-period and Multi-depot Vehicle Routing Problem with Time Window 
4.1 Introduction
4.2 Related Work
4.3 Genetic Algorithm for MDMPVRPTW
4.3.1 Overview of the Proposed Genetic Search Algorithm
4.3.2 Search Space
4.3.3 Chromosome Representation
4.3.4 Population Initialization
4.3.5 Evaluation and Selection Based on Fitness
4.3.6 Crossover
4.3.7 Mutation
4.4 Genetic Algorithm with Diversity Control for MDMPVRPTW
4.4.1 Overview of the Genetic Algorithm with Diversity Control
4.4.2 Search Space
4.4.3 Population Diversity Measure
4.4.4 Evaluation
4.4.5 Repair Procedure
4.4.6 Population Management
4.5 Computational results
4.5.1 Computational experiments of proposed GA
4.5.1.1 Results on small size instances
4.5.1.2 Investigation of crossover operator
4.5.1.3 Investigation of initial population
4.5.1.4 Sensitivity analysis of the parameters
4.5.2 Results of GA with Diversity Control
4.5.2.1 Parameter calibration
4.5.2.2 Results on field service routing instances
4.5.2.3 Sensitivity analysis on method components
4.6 Conclusion
Conclusions and Perspectives
Résumé Étendu en Français
References

GET THE COMPLETE PROJECT