【VRP problem 】 TWVRP problem is solved based on saving algorithm

Due to the continuous development of VRP problem, considering that demand points have requirements on vehicle arrival Time, the vehicle routing problem with Time window is added into the vehicle routing problem, which becomes VRP with Time Windows (VRPTW). The Vehicle Routing problem with Time Windows (VRPTW) is a time window constraint for the customer to be visited on the VRP. In the VRPTW problem, in addition to the driving cost, the cost function also includes the waiting time caused by arriving at a customer early and the service time required by the customer. In VRPTW, vehicles must not only meet the constraints of VRP problems, but also meet the Time Window constraints of demand points. The Time Window constraints of demand points can be divided into two types, one is Hard Time Window, which requires that vehicles must arrive within the Time Window. Early arrival must wait, while late arrival is rejected. The other is the Soft Time Window. It is not necessary to arrive in the Time Window, but to arrive outside the Time Window must be punished. The biggest difference between the Soft Time Window and the hard Time Window is to replace waiting and rejection with punishment.

Model 1 Problem definition:

The VRPTW is defined by a fleet of vehicles K={1,… A set of customers C={1,… ,n} , and a directed graph G, Typically the fleet is considered to be homogeneous, that is, all vehicles are identical. The graph consists of |C| + 2 vertices, where the customers are denoted 1, 2,… ,n and the depot is represented by the vertices 0 (“the starting depot”) and n + 1 (“the returning depot”). The set of All vertices, that is, 0,1… , n+1 is denoted N. The set of arcs, A, represents direct connections between the depot and the customers and among the customers. There are no arcs ending at Vertex 0 or originating from vertex n + 1. With each arc (I,j), where I ≠j, we associate a cost cij and a time tij, which may include service time at customer i.

Each vehicle has a capacity Q and each customer i a demand qi . Each customer i has a time window [ a i , b i] and a vehicle must arrive at the customer before bi . If it arrives before the time window opens, it has to wait until ai to service the customer. The time windows for both depots are assumed to be identical to [ a 0 , b 0] which represents the scheduling horizon. The vehicles may not leave the depot before a0 and must return at the latest at time bn+1 .

It is assumed that Q, ai , bi , qi , cij  are non-negative integers and tij are positive integers. Note that this assumption is necessary to develop an algorithm for the shortest path with resource constraints used in the column generation approach presented later. Furthermore it is assumed that the triangle inequality is satisfied for both cij  and tij .

The decision variable s ik is defined for each vertex i and each vehicle k and denotes the time vehicle k starts to service customer i. In case vehicle k does not service customer i, s ik has no meaning and consequently it’s value is considered irrelevant. We assume a0 = 0 and therefore s 0k  = 0, for all k. 

Model 2(refer to 2017 A generalized Formulation for Vehicle Routing Problems) :

The model is a 2-dimensional decision variable

C-w saving algorithm:

The basic idea is to connect each point separately with the source of goods, forming a number of lines containing only one distribution point, the total cost is twice the distance from the origin to each point cost; Then calculate the cost saving value of connecting point I and point J on the same line:

S (I, j) = Coi + Cio + Coj + Cjo – + + Cjo Cij (Coi) = Coi + Coj + CijS (I, j) = Coi + Cio + Coj + Cjo – + + Cjo Cij (Coi) = Coj Coi + + Cij

The specific steps are as follows: (1) Calculate the saving value S(I,j) and sort it from the largest to the smallest. (2) Consider the largest element Smax (I,j) Smax (I,j) in the table, corresponding points I and j, and operate according to the conditions: 1. If both I and j are not on the forming line, then the line o -> I ->j -> O is obtained, and then go to (3) 2. If I or J is on the constituted line, but not the interior point 0 -> I -> O, then it can be connected, go to (3) 3. If I and j are located on different formed lines, and neither of them is an interior point, then the line is connected and go to (3) 4. If I and J are on the same line formed, they will not be connected and go to (3) (3) row I and column J are crossed out, that is, point I cannot reach other points and point J cannot be reached by other stores. (4) If all elements are crossed out, a complete line is obtained and the algorithm terminates. Otherwise, select the largest element among the uncrossed elements and go to (2).

Rc208 = importData ('rc208.txt'); cap=1000; %% extracted data E=rc208(1,5); % distribution center time window start time L=rc208(1,6); % Distribution center time window end time vertexs=rc208(:,2:3); Customer =vertexs(2:end,:); Cusnum =size(customer,1); % Customer demands= RC208 (2:end,4); A =rc208(2:end,5); % customer time window start time [a[I],b[I]] b=rc208(2:end,6); % Customer time window end time [a[I],b[I]] s=rc208(2:end,7); % customer service time h=pdist(vertexs); dist=squareform(h); C [I][j]=dist[I][j] %% CW construct VRPTW initial solution [init_VC,init_TD, init_vL,violate_INTW]=init_TW(RC208, CAP); initNV=size(init_vc,1); Str1 =[' num2str(init_TD)]; Disp (str1) str2=[' number of vehicles used = 'num2str(initNV)]; Disp (str2) % % determine the optimal solution meets the time window constraints and capacity constraints, 0 means in violation of the constraints, flag = 1 to satisfy all constraints Judge (init_vc, cap, demands, a, b, m, s, dist); %% Check if there are elements missing in the optimal solution, missing elements, if not empty DEL=Judge_Del(init_vc); Vertexs =rc208(:,2:3); Draw_Best (init_vc,vertexs); tocCopy the code