FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Vehicle routing

Description
A transporter has to deliver heating oil from a refinery to a certain number of clients. The distances between the clients and the refinery and the demands in liters for the different sites are given. The transport company uses tankers with a capacity of 39000 liters for the deliveries. Determine the tours for delivering to all clients that minimize the total number of kilometers driven.

Further explanation of this example: 'Applications of optimization with Xpress-MP', Section 10.4 'Heating oil delivery' (e4deliver.mos)

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

Data Files

vrp_graph.mos

(!******************************************************
Mosel Example Problems
======================

file vrp.mos

TYPE:         Vehicle routing problem (VRP)
DIFFICULTY:   4
FEATURES:     MIP problem, formulation of constraints to eliminate
inadmissible subtours, definition of model cuts,
selection  with |', algorithm for printing the tours,
graphical solution representation
DESCRIPTION:  A transporter has to deliver heating oil from a refinery
to a certain number of clients. The distances between the
clients and the refinery and the demands in liters for
the different sites are given. The transport company uses
tankers with a capacity of 39000 liters for the deliveries.
Determine the tours for delivering to all clients that
minimize the total number of kilometers driven.
FURTHER INFO: Applications of optimization with Xpress-MP',
Section 10.4 Heating oil delivery'

(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2002, rev. Sep. 2017
*******************************************************!)

model "Heating oil delivery"
uses "mmxprs", "mmsvg"

declarations
NS = 7
SITES = 1..NS                       ! Set of locations, 1=refinery
CLIENTS = 2..NS

DEM: array(SITES) of integer        ! Demands
DIST: array(SITES,SITES) of integer ! Distances between locations
CAP: integer                        ! Lorry capacity

prec: array(SITES,SITES) of mpvar   ! 1 if i immediately precedes j,
! 0 otherwise
quant: array(CLIENTS) of mpvar      ! Quantity delivered up to i
end-declarations

initializations from 'vrp.dat'
DEM DIST CAP
end-initializations

! Objective: total distance driven
Length:= sum(i,j in SITES | i<>j) DIST(i,j)*prec(i,j)

! Enter and leave every city only once (except the depot)
forall(j in CLIENTS) EnterOnce(j):= sum(i in SITES| i<>j) prec(i,j) = 1
forall(i in CLIENTS) LeaveOnce(i):= sum(j in SITES| i<>j) prec(i,j) = 1

! If i is the first client of a tour, then quant(i)=DEM(i)
forall(i in CLIENTS) QuantFirst(i):= quant(i) <= CAP + (DEM(i)-CAP)*prec(1,i)

! If j comes just after i in a tour, then quant(j) is greater than the
! quantity delivered during the tour up to i plus the quantity to be
! delivered at j (to avoid loops and keep capacity limit of the tanker)
forall(i,j in CLIENTS| i<>j)
QuantSucc(i,j):= quant(j) >= quant(i) + DEM(j) - CAP +
CAP*prec(i,j) + (CAP-DEM(j)-DEM(i))*prec(j,i)

! If i is not the first client of a tour, quant(i) is larger than the sum
! of the quantities to deliver to i and to his predecessor on the tour
(!
declarations
modcut: array(CLIENTS) of linctr
end-declarations

forall(i in CLIENTS) do
modcut(i):= quant(i) >= DEM(i) + sum(j in SITES| i<>j) DEM(j)*prec(j,i)
setmodcut(modcut(i))
end-do
!)

forall(i in CLIENTS) do
quant(i) <= CAP
quant(i) >= DEM(i)
end-do

forall(i,j in SITES | i<>j) prec(i,j) is_binary

! Uncomment the following line to see the Optimizer log
! setparam("XPRS_VERBOSE",true)

! Solve the problem
minimize(Length)

! Solution printing
writeln("Total distance: ", getobjval)
forall(i in CLIENTS)
if(getsol(prec(1,i))>0) then
ct:=DEM(i)
writeln(1, " -> ", i)
p:=i
while(p<>1) do
n:= integer(round(sum(j in SITES) j*getsol(prec(p,j))))
writeln(p, " -> ", n)
ct+=DEM(n)
p:=n
end-do
writeln("Quantity delivered: ", ct)
end-if

! Solution drawing
declarations
X,Y: array(SITES) of integer        ! x-y-coordinates of sites
end-declarations

initializations from 'vrp.dat'
[X,Y] as 'POS'
end-initializations

minx:=min(i in SITES)X(i)-15; miny:=min(i in SITES)Y(i)-15
svgsetgraphviewbox(0, 0,
max(i in SITES)X(i)+15, max(i in SITES)Y(i)+25)
svgsetgraphscale(2)
svgsetgraphpointsize(2)

forall(i in CLIENTS) do
end-do

forall(i in CLIENTS)
if(getsol(prec(1,i))>0) then
p:=i
while(p<>1) do
n:= integer(round(sum(j in SITES) j*getsol(prec(p,j))))
`