Our project is focusing on conducting an optimized route for capacited transpotation problem. In particular, we are aiming to optimize under various conditions including optimized routing, optimized driving schedule with limited driving time, optimized time schedule, and optimized loading schedule. First, a little bit about project's history, background and why it is very important. Companies always try to deliver their goods to their customers in the most effecient way to cut down the cost and fulfil the customers' demand on time. Finding a scheme to transport goods in the most efficient way is a classical problem known as "Vehicle Routing Problem" (VRP). VRP is an extension of "Traveling Salesman Problem"(TSP) and has many variants. In this project, we particularly focus on a VRP variant called "Capacitated Vehicle Routing Problem" (CVRP). CVRP specifically examines the situation where multiple vehicles are used to deliver one type of commodity and each vehicle has uniform capacity and are considered identical (citations).
The background of our project is running a forest harvest company. Our Forest Harvest Company has 12 logging sites that are separated in 12 different areas and each logging site plants and produces one type of tree. Everyday, we will send out 3 vehicles from our only warehouse located at logging site 1 to pick up the trees cut at other logging sites. Each vehicle has uniform capacity and drives at the same speed. In other words, the vehicles are considered identical. These vehicles pick up the loads at each logging site in such way that (1) each site will only be visited once by one truck and the truck will pick up all its trees at once, (2) all logging sites must be visited, (3) all trucks must go back to the warehouse at the end of the day, and (4) the total number of demand of all logging sites visited by a truck does not exceed its capacity. Our project analysizes four scenarios where we aim to find the basic optimal routes, the optimal routes with distance limit, the optimal routes with shortest finish time, and the optimal routes with different priorities assigned to logging sites, respectively.
All the graphs are generated by Matlab. The code for Matlab can be seen at the help function section in Appendix.
There are total of four scenarios in the project. Each scenario is interconnected with more and more constraints added. In scenario 1, we will find a closed route for each truck so that (1) each site will only be visited once by one truck and the truck will pick up all its trees at once, (2) all logging sites must be visited, (3) all trucks must go back to the warehouse at the end of the day, and (4) the total number of requests that can be served in one route by a truck does not exceed the capacity of the truck. Our objective is to minimize the total distance traveled by all of the trucks while fulfiling all the requirements mentioned above.
In scenario 2, an additional distance limit constraint will be added to make sure that no driver will drive more than a specified distance everyday for safety. The distance limit is denoted as P in the following implementation. We will see in this section that how adding this extra constraint will affect the routes in which the trucks travel.
In scenario 3, the forest harvest company can only start shipping everyday harvest altogether to the customers until the last truck come back to the warehouse. Since we have the assumption that all trucks are identical and travel at the same speed, the length of the longest route taken by the truck determines the shipping time. In order to deliver orders to the customers as soon as possible, we aim to get the optimal traveling scheme which can minimize the finish time of all of the trucks.
In scenario 4, different priorities, indicated by S values, will be assigned to logging sites so that the logging sites with big S values should be visited prior to the logging sites with small values. This scenario is worth being discussed because vehicles used to transport trees may have open trunks, the drivers have to pick up big trees before small trees to assure the stability of their loads. In this section, we will show you how adding this additional constraint will affect the routes taken by the vehicles.
In this project, there will be several assumptions:
All the truck drivers will drive at the same speed.
All the trucks are identical, so they have the same capacity.
EO | BO | CO | WO | SO | SM | RM | SLM | RW | PP | BA | AE | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
EO | 0 | 6 | 11 | 10 | 27 | 15 | 21 | 19 | 26 | 19 | 31 | 33 |
BO | 6 | 0 | 12 | 11 | 29 | 22 | 25 | 23 | 3 | 21 | 32 | 35 |
CO | 11 | 12 | 0 | 19 | 32 | 21 | 30 | 24 | 31 | 25 | 34 | 34 |
WO | 10 | 11 | 19 | 0 | 30 | 21 | 24 | 28 | 30 | 20 | 33 | 34 |
SO | 27 | 29 | 32 | 30 | 0 | 32 | 29 | 32 | 35 | 31 | 35 | 36 |
SM | 15 | 22 | 21 | 21 | 32 | 0 | 29 | 22 | 28 | 26 | 33 | 35 |
RM | 21 | 25 | 30 | 24 | 29 | 29 | 0 | 25 | 32 | 29 | 33 | 35 |
SLM | 19 | 23 | 24 | 28 | 32 | 22 | 25 | 0 | 30 | 31 | 34 | 34 |
RW | 26 | 30 | 31 | 30 | 35 | 28 | 32 | 30 | 0 | 33 | 34 | 35 |
PP | 19 | 21 | 25 | 20 | 31 | 26 | 29 | 31 | 33 | 0 | 20 | 21 |
BA | 31 | 32 | 34 | 33 | 35 | 33 | 33 | 34 | 34 | 20 | 0 | 20 |
AE | 33 | 35 | 34 | 34 | 36 | 35 | 35 | 34 | 35 | 21 | 20 | 0 |
$\text{ Referring to the paper "Implementations of TSP-VRP Variants for Distribution Problem" published by the Mathematics Department}$
$\text{ at Universitas Negeri Malang, we modeled our problem as follows:
}$
$\textbf{Parameter definition:}$
$A$ = 12*12 matrix holding the distance information between different logging sites.
$dd[i]$ = the number of trees to be picked up at logging site i.
$K$ = the number of trucks
$N$ = the number of logging sites
$C$ = the capacity of each truck. (All trucks are identical in all of the scenarios examined in our project.)
$\textbf{Variable definition:}$
$x[i,j,k]= \begin{cases} 0 & \text{if truck 𝑘 drives from 𝑖 to 𝑗 }\\ 1 & \text{truck k does not drive from 𝑖 to 𝑗} \end{cases} $ $\text{ , } \forall k \in \text{K} \text{ , } \forall i \text{ , } j \in \text{N}$
$u[i,k]$= the load of the vehicle k after visiting logging site i $\text{ , } \forall k \in \text{K} \text{ , } \forall i \in \text{N}$
$\textbf{Constraint:}$
$\textbf{Objective function}$
$\text{The objective is to minimize the total distance traveled by all of the trucks} $
$$ \text{Min } \sum_{k=1}^K \sum_{i=1}^N \sum_{j=1}^N A[i,j]\cdot x[i,j,k]$$This is an MIP model.
Additional Constraint:
$$ \sum_{i=1}^N \sum_{j=1}^N A[i,j]\cdot x[i,j,k] \le P,\qquad \forall k \in \text{K} $$$v$ = the speed of trucks (in mile/hour)
$t$ = finish time of all of the trucks
This is an MIP model.
$S$ = indicate the sizes of trees
$Q$ = intermediate variable used to enforce a logic constraint (As I will show you shortly).
$\text{Meaning: If trees at logging site i are bigger than trees at logging site j, logging site i should be visited by truck k before logging site j be visited. }$
$\text{Transform the original constraint into a form that can be further translated into algebraic constraints:}$
$$\text{If S[i]}\ge \text{S[j], then Q[i,j,k] = 1} $$
$$\text{If S[i]} \le \text{S[j], then Q[i,j,k] = 0} $$
$$\text{If Q[i,j,k] = 1, then u[j,k]} \ge \text{u[i,k]+1 } $$
$$\forall k \in \text{K} \text{ , } \forall i \text{ , } j \in \text{logging site 2:N}$$
$$\text{Equivalent Algebraic Constraints}$$
$$S[i]-S[j]-1 \le 3\cdot Q[i,j,k]-(1-Q[i,j,k])$$
$$S[i]-S[j] \ge (-4)\cdot(1-Q[i,j,k])+Q[i,j,k]$$
$$u[j,k]-u[i,k]-1 \ge (-N)\cdot(1-Q[i,j,k])$$
$$\forall k \in \text{K} \text{ , } \forall i \text{ , } j \in \text{logging site 2:N}$$
$\text{The objective is to minimize the total distance traveled by all of the trucks} $
$$ \text{Min } \sum_{k=1}^K \sum_{i=1}^N \sum_{j=1}^N A[i,j]\cdot x[i,j,k]$$This is an MIP model.
using JuMP, Gurobi
A= readcsv("Location_Distance2.csv")
A=10*A
dd=[0 7 1 2 2 2 2 2 3 1 3 1] #Load await to be picked up at ith area (i=0,1,2...N)
k=3; #The number of trucks
N=12 #The number of areas
C=10; #Capacity of each truck. (All trucks are identical in all of the scenarios examined in our project.)
m1 = Model(solver = GurobiSolver(OutputFlag=0))
@variable(m1, x[1:N,1:N,1:k], Bin) # x[i,j,k]=1 means the truck k will travel from area i to area j in its route.
@variable(m1,1<=u[1:N,1:k]<=N,Int)
# u[i,k] represents the load of the vehicle k after visiting area i. we assign a u[i,k] to each of the areas.
#for kk=1:k
# @constraint(m1,sum(dd[i]*x[i,j,kk] for i=2:5, j=1:5)<=C)
#end
for kk=1:k
@constraint(m1,sum(dd[i]*x[j,i,kk] for i=2:N, j=1:N)<=C) #change made
#The total number of requests that can be served in one route by a vehicle does not exceed the capacity of the vehicle.
#This constraint imposes the capacity requirement.
end
for q=2:N
for r=2:N
for kk=1:k
@constraint(m1,u[q,kk]-u[r,kk]+1<=(N-1+1)*(1-x[q,r,kk]))
@constraint(m1,u[q,kk]-u[r,kk]+1>=(1-N+1)*(1-x[q,r,kk]))
#This constraint imposes the connectivity requirement.
end
end
end
for i in 2:N
@constraint(m1, sum( x[i,j,kk] for j in 1:N, kk=1:k ) == 1) #one out-edge
end
for j in 2:N
@constraint(m1, sum( x[i,j,kk] for i in 1:N, kk=1:k ) == 1) #one in-edge
end
for p=1:N
for kk=1:k
@constraint(m1,x[p,p,kk]==0) #no self-loops
end
end
for kk=1:k
@constraint(m1,sum(x[i,1,kk] for i in 2:N )==1)
# Each vehicle route begins and ends at the depot.
@constraint(m1,sum(x[1,j,kk] for j in 2:N )==1)
end
for kk=1:k
for h=2:N
@constraint(m1,sum(x[i,h,kk]-x[h,j,kk] for i=1:N, j=1:N)==0)
# The truck leaves an area must be the one that entered this area.
end
end
@objective(m1, Min, sum( A[i,j]*x[i,j,kk] for i in 1:N, j in 1:N, kk=1:k ))
# Minimize the total distance that k trucks will travel
status1=solve(m1)
println(status1)
println("The total distance that k trucks will travel is ",getobjectivevalue(m1), " miles.")
println(getvalue(u))
matrix=getvalue(x)
for kk=1:k
println("The distance that truck ",kk, " travels is ", sum(A[i,j]*matrix[i,j,kk] for i in 1:N, j in 1:N )," miles.")
end
println(matrix)
Optimal The total distance that k trucks will travel is 277.0 miles. [1.0 1.0 1.0; 1.0 1.0 1.0; 1.0 8.0 1.0; 1.0 1.0 1.0; 12.0 9.0 1.0; 1.0 12.0 12.0; 1.0 10.0 12.0; 1.0 11.0 12.0; 1.0 12.0 5.0; 12.0 12.0 2.0; 1.0 12.0 4.0; 1.0 12.0 3.0] The distance that truck 1 travels is 12.0 miles. The distance that truck 2 travels is 134.0 miles. The distance that truck 3 travels is 131.0 miles. [-0.0 1.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0; 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0] [-0.0 0.0 1.0 0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; 0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0; 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 0.0 -0.0; -0.0 -0.0 0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 0.0 -0.0] [-0.0 0.0 0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0; 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0; 1.0 -0.0 -0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 0.0; -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 1.0 -0.0]
# Each truck can only drive up to P miles per day.
P=110
m2 = Model(solver = GurobiSolver(OutputFlag=0))
@variable(m2, x[1:N,1:N,1:k], Bin) # x[i,j,k]=1 means the truck k will travel from area i to area j in its route.
@variable(m2,1<=u[1:N,1:k]<=N,Int)
# u[i,k] represents the load of the vehicle k after visiting area i. we assign a u[i,k] to each of the areas.
for kk=1:k
@constraint(m2,sum(dd[i]*x[j,i,kk] for i=2:N, j=1:N)<=C) #change made
#The total number of requests that can be served in one route by a vehicle does not exceed the capacity of the vehicle.
#This constraint imposes the capacity requirement.
end
for q=2:N
for r=2:N
for kk=1:k
@constraint(m2,u[q,kk]-u[r,kk]+1<=(N-1+1)*(1-x[q,r,kk]))
@constraint(m2,u[q,kk]-u[r,kk]+1>=(1-N+1)*(1-x[q,r,kk]))
#This constraint imposes the connectivity requirement.
end
end
end
for i in 2:N
@constraint(m2, sum( x[i,j,kk] for j in 1:N, kk=1:k ) == 1) #one out-edge
end
for j in 2:N
@constraint(m2, sum( x[i,j,kk] for i in 1:N, kk=1:k ) == 1) #one in-edge
end
for p=1:N
for kk=1:k
@constraint(m2,x[p,p,kk]==0) #no self-loops
end
end
for kk=1:k
@constraint(m2,sum(x[i,1,kk] for i in 2:N )==1)
# Each vehicle route begins and ends at the depot.
@constraint(m2,sum(x[1,j,kk] for j in 2:N )==1)
end
for kk=1:k
for h=2:N
@constraint(m2,sum(x[i,h,kk]-x[h,j,kk] for i=1:N, j=1:N)==0)
# The truck leaves an area must be the one that entered this area.
end
end
for kk=1:k
@constraint(m2,sum(A[i,j]*x[i,j,kk] for i=1:N, j=1:N)<=P)
# Each truck can only drive up to P miles per day.
end
@objective(m2, Min, sum( A[i,j]*x[i,j,kk] for i in 1:N, j in 1:N, kk=1:k ))
# Minimize the total distance that k trucks will travel
status2=solve(m2)
println(status2)
println("The total distance that k trucks will travel is ",getobjectivevalue(m2), " miles.")
println(getvalue(u))
matrix=getvalue(x)
for kk=1:k
println("The distance that truck ",kk, " travels is ", sum(A[i,j]*matrix[i,j,kk] for i in 1:N, j in 1:N )," miles.")
end
matrix
Optimal The total distance that k trucks will travel is 314.0 miles. [1.0 1.0 1.0; 1.0 1.0 1.0; 1.0 1.0 9.0; 1.0 4.0 12.0; 3.0 1.0 12.0; 1.0 1.0 10.0; 1.0 1.0 12.0; 1.0 1.0 11.0; 1.0 1.0 12.0; 1.0 3.0 12.0; 1.0 2.0 12.0; 2.0 1.0 12.0] The distance that truck 1 travels is 104.0 miles. The distance that truck 2 travels is 110.0 miles. The distance that truck 3 travels is 100.0 miles.
12×12×3 Array{Float64,3}: [:, :, 1] = -0.0 1.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 1.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 [:, :, 2] = -0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 1.0 -0.0 0.0 -0.0 -0.0 1.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 [:, :, 3] = -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0
v=10 #speed in mile/hour
m3 = Model(solver = GurobiSolver(OutputFlag=0))
@variable(m3, x[1:N,1:N,1:k], Bin) # x[i,j,k]=1 means the truck k will travel from area i to area j in its route.
@variable(m3,1<=u[1:N,1:k]<=N,Int)
# u[i,k] represents the load of the vehicle k after visiting area i. we assign a u[i,k] to each of the areas.
@variable(m3,t) # finish time
for kk=1:k
@constraint(m3,sum(dd[i]*x[j,i,kk] for i=2:N, j=1:N)<=C) #change made
#The total number of requests that can be served in one route by a vehicle does not exceed the capacity of the vehicle.
#This constraint imposes the capacity requirement.
end
for q=2:N
for r=2:N
for kk=1:k
@constraint(m3,u[q,kk]-u[r,kk]+1<=(N-1+1)*(1-x[q,r,kk]))
@constraint(m3,u[q,kk]-u[r,kk]+1>=(1-N+1)*(1-x[q,r,kk]))
#This constraint imposes the connectivity requirement.
end
end
end
for i in 2:N
@constraint(m3, sum( x[i,j,kk] for j in 1:N, kk=1:k ) == 1) #one out-edge
end
for j in 2:N
@constraint(m3, sum( x[i,j,kk] for i in 1:N, kk=1:k ) == 1) #one in-edge
end
for p=1:N
for kk=1:k
@constraint(m3,x[p,p,kk]==0) #no self-loops
end
end
for kk=1:k
@constraint(m3,sum(x[i,1,kk] for i in 2:N )==1)
# Each vehicle route begins and ends at the depot.
@constraint(m3,sum(x[1,j,kk] for j in 2:N )==1)
end
for kk=1:k
for h=2:N
@constraint(m3,sum(x[i,h,kk]-x[h,j,kk] for i=1:N, j=1:N)==0)
# The truck leaves an area must be the one that entered this area.
end
end
#minimize the finish time
for kk=1:k
@constraint(m3,t>=(sum(A[i,j]*x[i,j,kk] for i in 1:N, j in 1:N)/v))
end
@objective(m3, Min, t)
status3=solve(m3)
println(status3)
println("The finish time is ",getobjectivevalue(m3)," hours.")
matrix=getvalue(x)
println("The total distance that ",k, " trucks will travel is ",sum( A[i,j]*matrix[i,j,kk] for i in 1:N, j in 1:N, kk=1:k ), " miles.")
for kk=1:k
println("The distance that truck ",kk, " travels is ", sum(A[i,j]*matrix[i,j,kk] for i in 1:N, j in 1:N )," miles.")
end
matrix
Optimal The finish time is 10.8 hours. The total distance that 3 trucks will travel is 316.0 miles. The distance that truck 1 travels is 108.0 miles. The distance that truck 2 travels is 104.0 miles. The distance that truck 3 travels is 104.0 miles.
12×12×3 Array{Float64,3}: [:, :, 1] = -0.0 -0.0 -0.0 0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 [:, :, 2] = -0.0 1.0 0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 [:, :, 3] = -0.0 0.0 0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0
S=[0 1 3 1 5 1 1 3 1 5 5 1]
m4 = Model(solver = GurobiSolver(OutputFlag=0))
@variable(m4, x[1:N,1:N,1:k], Bin) # x[i,j,k]=1 means the truck k will travel from area i to area j in its route.
@variable(m4,1<=u[1:N,1:k]<=N,Int)
# u[i,k] represents the load of the vehicle k after visiting area i. we assign a u[i,k] to each of the areas.
@variable(m4,Q[1:N,1:N,1:k],Bin)
for kk=1:k
@constraint(m4,sum(dd[i]*x[j,i,kk] for i=2:N, j=1:N)<=C) #change made
#The total number of requests that can be served in one route by a vehicle does not exceed the capacity of the vehicle.
#This constraint imposes the capacity requirement.
end
for q=2:N
for r=2:N
for kk=1:k
@constraint(m4,u[q,kk]-u[r,kk]+1<=(N-1+1)*(1-x[q,r,kk]))
@constraint(m4,u[q,kk]-u[r,kk]+1>=(1-N+1)*(1-x[q,r,kk]))
#This constraint imposes the connectivity requirement.
end
end
end
for i in 2:N
@constraint(m4, sum( x[i,j,kk] for j in 1:N, kk=1:k ) == 1) #one out-edge
end
for j in 2:N
@constraint(m4, sum( x[i,j,kk] for i in 1:N, kk=1:k ) == 1) #one in-edge
end
for p=1:N
for kk=1:k
@constraint(m4,x[p,p,kk]==0) #no self-loops
end
end
for kk=1:k
@constraint(m4,sum(x[i,1,kk] for i in 2:N )==1)
# Each vehicle route begins and ends at the depot.
@constraint(m4,sum(x[1,j,kk] for j in 2:N )==1)
end
for kk=1:k
for h=2:N
@constraint(m4,sum(x[i,h,kk]-x[h,j,kk] for i=1:N, j=1:N)==0)
# The truck leaves an area must be the one that entered this area.
end
end
for kk=1:k
for q=2:N
for r=2:N
@constraint(m4,S[q]-S[r]-1<=3*Q[q,r,kk]-(1-Q[q,r,kk]))
@constraint(m4,S[q]-S[r]>=(-4)*(1-Q[q,r,kk])+Q[q,r,kk])
@constraint(m4,u[r,kk]-u[q,kk]-1>=(-N)*(1-Q[q,r,kk]))
end
end
end
@objective(m4, Min, sum( A[i,j]*x[i,j,kk] for i in 1:N, j in 1:N, kk=1:k ))
# Minimize the total distance that k trucks will travel
status4=solve(m4)
println(status4)
println("The total distance that k trucks will travel is ",getobjectivevalue(m4), " miles.")
println(getvalue(u))
matrix=getvalue(x)
for kk=1:k
println("The distance that truck ",kk, " travels is ", sum(A[i,j]*matrix[i,j,kk] for i in 1:N, j in 1:N )," miles.")
end
matrix
Optimal The total distance that k trucks will travel is 300.0 miles. [1.0 1.0 1.0; 12.0 3.0 12.0; 5.0 2.0 11.0; 12.0 12.0 12.0; 3.0 1.0 1.0; 12.0 8.0 12.0; 12.0 11.0 12.0; 4.0 2.0 2.0; 12.0 9.0 12.0; 1.0 1.0 1.0; 2.0 1.0 1.0; 12.0 10.0 12.0] The distance that truck 1 travels is 141.0 miles. The distance that truck 2 travels is 147.0 miles. The distance that truck 3 travels is 12.0 miles.
12×12×3 Array{Float64,3}: [:, :, 1] = -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 1.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 1.0 0.0 -0.0 0.0 0.0 0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 0.0 -0.0 -0.0 1.0 -0.0 0.0 0.0 0.0 -0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 1.0 0.0 -0.0 0.0 -0.0 0.0 1.0 0.0 0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 [:, :, 2] = -0.0 -0.0 0.0 -0.0 0.0 1.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 -0.0 0.0 -0.0 -0.0 0.0 0.0 -0.0 0.0 0.0 0.0 0.0 -0.0 1.0 0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 0.0 0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 1.0 0.0 0.0 -0.0 -0.0 -0.0 0.0 1.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 1.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 0.0 0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 1.0 0.0 -0.0 0.0 0.0 -0.0 [:, :, 3] = -0.0 1.0 0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 -0.0 1.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 0.0 0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 -0.0 -0.0 0.0 -0.0 -0.0 -0.0 -0.0 0.0 0.0 -0.0 -0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 -0.0 0.0 0.0 -0.0 0.0 -0.0 -0.0 0.0 -0.0 0.0 -0.0 0.0 0.0 0.0 0.0 0.0 -0.0
From running the code in previous session, we generate a matrix for each truck that describes the order of the logging sites that it drives through. The graph below is generated by Matlab. Each color represents the route of a truck. In this case, the red path represents the route of truck 1; the blue path represents the route of truck 2; the green path represents the route of truck 3.
In this session, we have:
The distance for truck 1 is 12 miles.
The distance for truck 2 is 134 miles.
The distance for truck 3 is 131 miles.
From running the code in previous session, we generate a matrix for each truck that describes the order of the logging sites that it drives through. The graph below is generated by Matlab. Each color represents the route of a truck. In this case, the red path represents the route of truck 1; the blue path represents the route of truck 2; the green path represents the route of truck 3.
In this session, we impose an extra constraint to make sure that each truck driver work in roughly equal hours.
The distance for truck 1 is 104 miles.
The distance for truck 2 is 111 miles.
The distance for truck 3 is 100 miles.
From running the code in previous session, we generate a matrix for each truck that describes the order of the logging sites that it drives through. The graph below is generated by Matlab. Each color represents the route of a truck. In this case, the red path represents the route of truck 1; the blue path represents the route of truck 2; the green path represents the route of truck 3.
In this session, we impose two more varibles: speed and time. The assumption we have is that our well-trained drivers will drive at the same speed. We want to minimize the time used by each driver to return to our warehouse (logging site 1).
The distance for truck 1 is 108 miles.
The distance for truck 2 is 104 miles.
The distance for truck 3 is 104 miles.
As we can see, in this optimized solution, the distance for each driver is more equally distributed.
From running the code in previous session, we generate a matrix for each truck that describes the order of the logging sites that it drives through. The graph below is generated by Matlab. Each color represents the route of a truck. In this case, the red path represents the route of truck 1; the blue path represents the route of truck 2; the green path represents the route of truck 3.
$\text{The result from scenario 4 shows the three routes as follows: }$
$\text{route 1: 1 ->10 ->11 ->5 ->8 ->3 ->1}$
$\text{route 2: 1 ->6 ->9 ->12 ->7 ->4 ->1}$
$\text{route 3: 1 ->2 ->1}$
$\text{As you can see, these routes follow the priority order indicated by S value (i.e. {11, 10, 5}>{3, 8}>{1, 2, 4, 6, 7, 9, 12})}$
Overall, we managed to solve for the optimized solution and route under some real-life conditions. The model we used is capacited vehicle routing problem, which allows us to have vehicles that have uniform capacty and only visit each site once. For each part of the problems in this project, we add more and more constriants and refinations so that we have a tradeoff between the real-life conditions and performance. The more real we model our problem, the more constraints that we have to add. As we discovered, the more constriants we add to minimize the time used in our routing problem, the more equalized diatance we get for each truck. It is a solution very interesting to notice. Unfortunatly, if we extand our interest in making the problem more real, we will encounter some nonlinear constraints and cost functions that are very tough to deal with.
There are many questions that we can consider in the future. For example, how to add the time variable since trees have different rate of growth and the transportation time, speeds and distance can also vary? How to add cost into the scenerio like gas fee, variable labor cost etc. In addition, we can test our model with larger and extanded amount of data.
## Matlab code for generating graphs
%%
I = imread('arizona-rivers-map.png','png');
loggingpos = [120 248; 160 98; 280 83; 300 210; 250 370;90 450;98 590;
390 400; 400 300; 300 480;230 550;300 600];
color = {'black'};
I2 = insertMarker(I,loggingpos,'x','color',color,'size',10);
image(I2)
hold on
x1=[120 248];
y1=[160 98];
line(x1,y1);
hold off
%imshow(I2);
position = [110 238 30 30;150 88 30 30; 270 73 30 30; 290 200 30 30;
240 360 30 30;80 440 30 30;88 580 30 30;380 390 30 30;
390 290 30 30; 290 470 30 30;220 540 30 30;290 590 30 30];
label = cell(12,1);
val = [1 2 3 4 5 6 7 8 9 10 11 12];
for ii = 1:12
label{ii} = ['site: ' num2str(val(ii))];
end
I3 = insertObjectAnnotation(I2,'rectangle',position,label);
imshow(I3);
figure(1)
hold on
%Part 1
% Truck 1: 1-2-1
p11 = [120 160];
p12 = [248 98];
line(p11,p12,'Color','r','LineWidth',2)
%plot([p11(2),p12(2)],[p11(1),p12(1)],'Color','r','LineWidth',2);
% Truck 2:1-3-5-7-8-6-1
p21 = [120 280 250 98 390 90 120];
p22 = [248 83 370 590 400 450 248];
line(p21,p22,'Color','b','LineWidth',2)
%plot([p21(2),p22(2)],[p21(1),p22(1)],'Color','b','LineWidth',2);
% Truck 3: 1-4-10-12-11-9-1
p31 = [120 300 300 300 230 400 120];
p32 = [248 210 480 600 550 300 248];
line(p31,p32,'Color','g','LineWidth',2)
hold off
% Part2
% Truck 1: 1-2-12-5-1
p11 = [120 160 300 250 120];
p12 = [248 98 600 370 248];
line(p11,p12,'Color','r','LineWidth',2)
% Truck 2: 1-9-11-10-4-1
p21 = [120 400 230 300 300 120];
p22 = [248 300 550 480 210 248];
line(p21,p22,'Color','b','LineWidth',2)
%Truck 3: 1-3-6-8-7-1
p31 = [120 280 90 390 98 120];
p32 = [248 83 450 400 590 248];
line(p31,p32,'Color','g','LineWidth',2)
% Part 3
% Truck 1: 1-6-9-8-3-1
p11 = [120 90 400 390 280 120];
p12 = [248 450 300 400 83 248];
line(p11,p12,'Color','r','LineWidth',2)
% Truck 2: 1-2-5-12-1
p21 = [120 160 250 300 120];
p22 = [248 98 370 600 248];
line(p21,p22,'Color','b','LineWidth',2)
%Truck 3: 1-4-10-11-7-1
p31 = [120 300 300 230 98 120];
p32 = [248 210 480 550 590 248];
line(p31,p32,'Color','g','LineWidth',2)
% Part 4
% Truck 1: 1-10-11-5-8-3-1
p11 = [120 300 230 250 390 280 120];
p12 = [248 480 550 370 400 83 248];
line(p11,p12,'Color','r','LineWidth',2)
% Truck 2: 1-6-9-12-7-4-1
p21 = [120 90 400 300 98 300 120];
p22 = [248 450 300 600 590 210 248];
line(p21,p22,'Color','b','LineWidth',2)
%Truck 3: 1-2-1
p31 = [120 160 120];
p32 = [248 98 248];
line(p31,p32,'Color','g','LineWidth',2)
Unrecognized magic %imshow
.
Julia does not use the IPython %magic
syntax. To interact with the IJulia kernel, use IJulia.somefunction(...)
, for example. Julia macros, string macros, and functions can be used to accomplish most of the other functionalities of IPython magics.
Unrecognized magic %Part
.
Julia does not use the IPython %magic
syntax. To interact with the IJulia kernel, use IJulia.somefunction(...)
, for example. Julia macros, string macros, and functions can be used to accomplish most of the other functionalities of IPython magics.
Unrecognized magic %plot
.
Julia does not use the IPython %magic
syntax. To interact with the IJulia kernel, use IJulia.somefunction(...)
, for example. Julia macros, string macros, and functions can be used to accomplish most of the other functionalities of IPython magics.
Unrecognized magic %plot
.
Julia does not use the IPython %magic
syntax. To interact with the IJulia kernel, use IJulia.somefunction(...)
, for example. Julia macros, string macros, and functions can be used to accomplish most of the other functionalities of IPython magics.
Unrecognized magic %Truck
.
Julia does not use the IPython %magic
syntax. To interact with the IJulia kernel, use IJulia.somefunction(...)
, for example. Julia macros, string macros, and functions can be used to accomplish most of the other functionalities of IPython magics.
Unrecognized magic %Truck
.
Julia does not use the IPython %magic
syntax. To interact with the IJulia kernel, use IJulia.somefunction(...)
, for example. Julia macros, string macros, and functions can be used to accomplish most of the other functionalities of IPython magics.
Unrecognized magic %Truck
.
Julia does not use the IPython %magic
syntax. To interact with the IJulia kernel, use IJulia.somefunction(...)
, for example. Julia macros, string macros, and functions can be used to accomplish most of the other functionalities of IPython magics.