Multi-splitting delivery for the vehicle routing problem - Dissertation sur la Science

The vehicle Routing Problem is a problem of combinatorial optimization and operational research, widely studied for several years as well as its variants. With increasing distribution flows, many logistics applications require customers to be bundled into clusters which facilitate delivery or any upstream or downstream processing of customers. There is therefore a clustered vehicle routing problem which is a generalization of the vehicle routing problem in which the clients are clusteredclustered, and all the clients of a cluster must be served consecutively by at least one vehicle.

Several works have been done to deal with this type of problem: cluster-first route-second, route-first cluster-second and order-first split-second methods.In this paper, from a simple example, we give an illustration of the multi-split delivery problem. This example presents the new concept of overlapping clustered vehicle routing problems which can be considered as an extension of the previous works. We give also a mathematical formulation of this type of problem.

In this paper, from a simple example, we give an illustration of the multi-splitting delivery problem for overlapping clustered vehicle routing problems which can be considered as an extension of this work as well as a formulation mathematical of this type of problem. A two-level variant will be presentedpresented, and we propose a heuristic/ metaheuristic algorithm inspired by those proposed in the references below.

Our paper is organized as follow: After giving a simple motivation example to contribution in this paper is to propose a mathematical formulation of the problem of multi-splitting delivery for the problem of clustered vehicle tours. To do this we start by giving simple examples to illustrate the gain obtained. Then we give a mathematical formulation that differs a little from other formulations.

Keywords: Vehicle Routing Problem, delivery splitting procedure, clustering, cluster-first route-second, route-first cluster-second, heuristic approach. Example of motivation – We will work on a simple illustration example:FIG. 1 – case (A) and case (B)In this figure: o denotes the depot, a, b and c denote the customers. We worked on two examples. In the first case, it is assumed that each customer has a demand of two units and vehicles with a capacity of 3 units are available. It is clear that the optimal solution without splitting is to serve each customer at a time with 3 vehicles (case (A)). And if we impose to do a fractionation we will have to use only 2 vehicles (case (B)).

In the second example we

assume that client A has a request of 2, client B has a request of 6 and client C has a request of 2. In the same way, it is shown that without splitting, we will have to use 3 vehicles while with splitting we will have only 2 vehicles.Formulation mathematicConsider the graph G = (V, A), where V = {0, …, n} = C ∪ {0} the set of nodes and A = {(i, j) | i, j ∈ V} is the set of arcs. Each node i ∈ C represents a client and node 0 corresponds to the depot. The problem is to solve:(4) : under constraint of cluster constructionwith :Qkthe capacity of the vehicle klikrepresents the allocation of the request of the nodej on the road kdijdistance/ cost associated with the arc (i, j)Nnumber of nodesKnumber of vehiclesDjdemand of the node j.

The approach used: The most reasonable strategy, given the complexity of calculating the optimal solution, is to design heuristic procedures. We assume that we have the following property: We use the following Clarke and Wright heuristics:But for our formulation, we will modify it as follows: The heuristic is defined as follows: Calculate (7) for i, j = 1, …, NOrder the entries obtained in 1) in descending order, Let δlm be the larget,if l equals m, we do not partition,if l is different from m partioning is done according to the position of m and l on the road in question.

Accéder à l'échantillon complet