Programming Assignment
The due date: 10:00am, Tuesday, 31th of October 2017.
This assignment is worth of 15% of the total course mark.
1 Introduction
The goal of this programming assignment is to make you familiar with research and devel-
opment work, yet give you experience in solving practice-oriented optimisation problems
and writing technical reports. It deals with a variant of the Vehicle Routing Prob-
lem, called the Capacitated Vehicle Routing Problem with two-dimensional loading con-
straints, or 2L-CVRP for short. The problem requires determining the optimal set of
routes, for a homogenous eet of vehicles, to serve a set of customers with known de-
mands of items. The designed routes must originate and terminate at the central depot,
and totally satisfy customer demand. Each customer must be visited once by one vehicle
only. The total demand of the customer set, covered by a route, must not exceed the maxi-
mum carrying load of the assigned vehicle. The 2L-CVRP problem models the case when
the demand of customers consists of two-dimensional rectangular and weighted items.
The aim of the problem is to generate a set of routes that respect the aforementioned
constraints and also guarantee the feasible loading/unloading of the items into/from the
vehicles. It is a practical problem that nds its application in the eld of transportation
logistics. From the theoretical point of view, this is an NP-hard combinatorial opti-
mization problem; it is unlikely that large instances can be solved to optimality in short
computational time. The problem has been widely studied by Zachariadis et al. (2009);
Leung et al. (2013); Duhamel et al. (2011); Fuellerer et al. (2009); Gendreau et al. (2008);
Dominguez et al. (2014) and other academics and practitioners.
Because solving the problem exactly is a hard task, you are asked to develop and im-
plement an approximate heuristic algorithm. It should solve the problem quite well in
reasonable time, though optimality may be not achieved. To solve the problem, you may
either propose your own algorithmic approach or adopt one from the literature. To study
the existing techniques, you may refer to the papers attached. You are allowed to work
in a team of two students on this assignment, moreover, we encourage you to do this
to improve your teamwork skills. At the same time, we expect you to work cooperatively
with your partner so that you both study from each other and share your ideas rather
than just simply split the work. Both members must be familiar with every part of the
project and its code. Individual work is also allowed, but will be treated in the same way
as a team work.
2 Formal Problem Statement
The 2L-CVRP problem can be de ned as follows. Let G = (V;E) be an undirected
graph, where V is the vertex set containing the central depot and n customers, and
1
COMP SCI 2203 - Problem Solving Software Development Semester 2, 2017
the length dimension of the vehicle surface. In other words,
no item of customer j, visited after customer i, can be
placed between items of customer i and the rear part (load-
ing door) of the vehicle.
The sequence constraint arises in practice, when it is not
feasible to move items inside the vehicle, due to their
weight or fragility. In these cases, the unloading of every
item must be accomplished without any repositioning of
other items. Fig. 1 demonstrates the two versions of the
2L-CVRP. In particular, Fig. 1 demonstrates a route visit-
ing three customers 1–3. Customer 1 demands items I
11
, I
12
and I
13
, customer 2 demands items I
21
and I
22
, and cus-
tomer 3 demands items I
31
and I
32
. Let (0,0) correspond
to the front left corner of the loading surface. The position
of an item is expressed as the coordinate pair (w
pos
,l
pos
)
where w
pos
denotes the W-axis position and l
pos
denotes
the L-axis position of the item’s left front corner. In Load-
ing A, for example, item I
22
is placed at (0,0). Loading A is
a feasible unrestricted packing but it violates the constraint
posed for the Sequential version of the problem. To be pre-
cise, item I
32
obstructs the unloading of items I
12
and I
22
,
while item I
31
obstructs the unloading of item I
22
. On the
other hand, Loading B is a feasible loading for both the
Unrestricted, and the Sequential versions of the problem.
Items I
11
, I
12
and I
13
are the first to be unloaded, followed
by I
21
and I
22
, and finally I
31
and I
32
.
3. The proposed algorithm
Due to the high complexity of both the VRP and the
BPP variants, exact methodologies become inapplicable
for solving large scale instances of the 2L-CVRP, that often
arise in practice. Therefore, to solve such large scale prob-
lems, one’s interest should be focused on metaheuristic
methodologies that are able to produce near optimal solu-
tions within reasonable computing time. Analytic surveys
on the solution approaches designed for the VRP were
published by Gendreau et al. (2002) and Cordeau et al.
(2004). As mentioned in the first section, in terms of the
routing aspects of the 2L-CVRP, our algorithmic frame-
work explores the solution space by employing Tabu
Search combined with a guiding mechanism that is based
on the Guided Local Search principles (Voudouris and
Tsang, 1996). This guiding strategy controls the objective
function of the problem by penalising low-quality features
present in the current solution. Regarding the loading con-
straints of the problem, we designed a bundle of packing
heuristics that produce diverse packing structures in order
to generate a feasible loading of the items onto the loading
surface.
3.1. Packing heuristics bundle
To determine whether a route-sequence of customers-is
feasible in terms of the loading constraints of the examined
problem, we designed five packing heuristics. Given a cus-
tomer sequence rt, and its corresponding set of items IS
rt
,
these heuristics try to generate diverse packing structures,
in order to increase the probability of obtaining a feasible
loading. If all of the packing heuristics fail to produce
any feasible loading, the route examined is considered to
violate the loading constraints of the problem. In particu-
lar, given a route, the packing procedure starts by generat-
ing two orderings (Ord
Seq
,Ord
Un
) of all items demanded by
the set of customers covered by this route. Let the term visit
order denote the position of a customer-and its correspond-
ing items-within its route. For example, in Fig. 1, customer
3 is the third one to be visited by the vehicle; therefore the
visit order of customer 3 and its demanded items I
E.E. Zachariadis et al./European Journal of Operational Research 195 (2009) 729–743 731
Figure 1: The Unrestricted and Sequential loadings.
E =f(i;j) : i;j2Ng is the edge set. With each edge (i;j)2E is associated a distance
dij from vertex i to vertex j. In the central depot, a eet of q homogenous vehicles is
available. Every vehicle has a maximum carrying load equal to C and a rectangular
loading surface of length L and width W. The demand of each customer i, i = 1;:::;n,
consists of a set Si of mi rectangular items of total weight Bi. Each item sai 2 Si,
a = 1;:::;mi, has length lai and width wai. The items must be placed on the loading
surfaces without being rotated: their l- and w-edges must be parallel to the L- and W-
edges of the vehicle surfaces, respectively. This constraint models the practical cases of
automated, xed orientation palette loading. The 2L-CVRP aims at determining the set
of routes minimizing the total distance and satisfying the following constraints:
the size of the generated route set must not exceed the number of available vehicles
q (though less than q vehicles can be used in total);
every route starts and ends at the central depot and employs one vehicle;
the demand of every customer is totally covered;
each customer must be visited only once;
the total weight of all items demanded by the set of customers covered by a route
must not exceed the capacity C;
there must be a non-overlapping loading of all items demanded by the set of cus-
tomers covered by a route into the L W loading surface of the vehicle.
The 2L-CVRP problem has two versions concerning possible loading: the unrestricted
2L-CVRP and the sequential 2L-CVRP. The unrestricted version is modelled by the
aforementioned six constraints, while for the sequential version of the problem an addi-
tional constraint, namely Sequence Constraint is imposed: the loading of the items must
ensure that whenever a customer i is visited, all items in the set Si can be unloaded by
employing a sequence of straight movements (one per item) parallel to the length dimen-
sion of the vehicle surface. In other words, no item of customer j, visited after customer
i, can be placed between items of customer i and the rear part (loading door) of the
vehicle.
2
COMP SCI 2203 - Problem Solving Software Development Semester 2, 2017
The sequence constraint arises in practice, when it is not feasible to move items inside the
vehicle, due to their weight or fragility. In these cases, the unloading of every item must
be accomplished without any repositioning of other items. Figure 1 compares the two
versions of loading. In particular, it depicts a route visiting three customers. Customer
1 demands items s11, s12 and s13, customer 2 demands items s21 and s22, and customer
3 demands items s31 and s32. Let (0;0) correspond to the front left corner of the loading
surface. The position of an item is expressed as the coordinate pair (xai;yai), where xai
denotes the W-axis position and yai denotes the L-axis position of the left front corner
of item sai of customer i. In Loading A, for example, item s22 is placed at (0;0). It
is a feasible unrestricted packing, but it violates the constraint posed for the sequential
version of the problem. To be precise, item s32 obstructs the unloading of items s12 and
s22, while item s31 obstructs the unloading of item s22. On the other hand, Loading B is
a feasible loading for both the unrestricted and the sequential versions of the problem.
Items s11, s12 and s13 are the rst to be unloaded, followed by s21 and s22, and nally s31
and s32.
3 Speci cation
To succeed in this assignment, you must complete both of its parts: the programming
part and the report. Lack of any part will cause zero scores awarded for this assignment.
The rst part asks you to develop an algorithm which solves the problem approximately
with regard to the unrestricted and the sequential loading. Then, you need to implement
and test your algorithm to ensure that solutions it returns are feasible and correct. Your
program will be checked manually later on. In the second part, you need to evaluate the
performance of your algorithm in terms of its quality and speed by running computational
experiments on benchmark instances. For this purpose, 180 instances divided into 5
classes are attached. There are small and large instances in order to test your approach
for di erent input size. Your next step is to compare your solutions with some state-
of-the-art results. Using the comparison, you should be able to draw conclusions on the
e ciency of your approach, decide on which test instances seem to be easier or harder to
solve and why, and discuss on how your approach can be potentially improved. Finally,
you must write a technical report. Though you may adopt the design of your algorithm
from the literature and implement it, you must report the ndings in your own language.
Therefore, you are not allowed to straightly copy from any paper or material. You must
present your best solution for each of the test instances. The feasibility of your solutions
will be later checked automatically by the web-submission system. Ensure that they are
correct, otherwise you may loose scores. To estimate the size of the report, set its font
size to 12 pt and line spacing to 1. The report must be submitted in PDF format.
Exercise 1 Writing the abstract (worth of 15%)
You must start your report with an abstract. This should give you skills in explaining
key ideas brie y. First, you need to outline your algorithm on conceptual level and talk
about the techniques applied. It can be worth to mention your approaches to handle the
loading component. You then need to summarily explain the idea behind the generation
of the route set. It should be done on a high level so that readers get an idea what you
3
COMP SCI 2203 - Problem Solving Software Development Semester 2, 2017
do, but still need to read the rest for particular details. Therefore, reporting algorithmic
strategies and the way how you construct solutions (iteratively, sequentially, randomly are
some keywords) is helpful. You may start with your loading strategy, discussing it in 3-4
sentences, then spend another 3-4 sentences to cover your whole approach. You should
nally mention the results of computational experiments along with the main outcomes
of your project. Here, you should brie y describe the performance of your algorithm
compared to existing approaches from the literature. In total, the abstract should not
exceed a half-page in size. It should be concise and comprehensive.
Writing an abstract is an art. Indeed, it could be easier to start is a very raw draft and
return back to it when all the subsequent sections of the report are nished.
Exercise 2 Addressing the unrestricted packing component (worth of 10%)
In this section, you need to explain your strategy to resolve the unrestricted loading
problem. You may nd that the two-stage problem-solving strategy is commonly applied
for this problem in research literature. This assumes solving the routing part rst, then
checking its feasibility regarding the loading constraints. Speci cally, the rst stage
allocates a number of vehicles, assigns customers to the vehicles, and orders the customers
to build the routes. The second stage is usually implemented in the form. of a subroutine,
which solves the loading decision problem for each route accepting the corresponding
items as an input. If loading is feasible for every route, then the whole solution is valid.
Thus, it is very likely that your approach to the 2L-CVRP will follow the same way.
Therefore, your task is to develop the subroutine, which you think is to be e cient, then
describe it in the report. In fact, the subroutine should solve the decision version of the
so-called Two-Dimensional Bin Packing Problem, which has various heuristic solutions
you may nd in the internet.
To explain your algorithm for the loading component in a proper way, you should use a
pseudocode or a diagram accompanied with a text description. You need to write 1-1.5
pages in total. You may feel it rather di cult to start your report and introduce your
algorithm. If so, have a look at the papers attached rst. Many of them explain similar
loading (packing) strategies, and you may adopt their style. and notation. Again, your
description should be concise yet signi cant for a reader to understand and reproduce
your algorithm. You may also discuss the complexity of your subroutine as a function of
given items and gure out potential methods to speed up its work.
Exercise 3 Addressing the sequential packing component (worth of 10%)
Similarly to the previous exercise, you need to detail your strategy for the sequential
loading problem.
Exercise 4 Solving the 2L-CVRP problem (worth of 20%)
Here, you need to detail your approach for the 2L-CVRP. The structure of your algorithm
should dictate how to do this. For example, you may consecutively describe all the steps
rst, then give details for every step. If the approach starts with an initial or a partial
solution, you should mention this fact as well as how such solution is to be generated.
4
COMP SCI 2203 - Problem Solving Software Development Semester 2, 2017
When the approach is iterative, you need clearly explain the iterative step and specify
the conditions which terminate its work. When the approach is recursive, explain its
recursive step and note the base case. If the algorithm is randomised, explain all the
potential actions it may undertake. You also must address all the control parameters, if
any are utilized in the approach. The way how the algorithm constructs solutions must be
comprehensive. Again, pseudocodes, diagrams, and schemes are to be used to augment
the text description. You need to write at most two pages.
Exercise 5 Running computational experiments (worth of 25%)
This is to be the last section of you report which requires to evaluate the performance of
your algorithm for the 2L-CVRP. Your task is to apply your algorithm to every instance
of the provided benchmark suit. If your algorithm is deterministic, i.e. it always returns
the same result for a xed input, you may compute each instance only once. Alternatively,
your approach may be randomised, thus returning di erent results for a same input. In
this case, you have to run your algorithm for each instance multiple times; 10 times
should be enough assuming that computations might be costly. For each instance, you
then have to report the best, the worst, and the average objective values that have been
obtained. Proceed similarly to calculate the best, the worst, and the average running
times.
Compare your results with the state-of-the-art. You can nd results of other approaches
reported in the tables of the research papers attached. Your task is to compare with at
least one another algorithm. You should then form. a table where the objective values
of your approach and of those you compare with are reported. You also need to publish
the relative gaps between objective values of the solutions and the best known result.
The gap can be calculated as follows: 100 ALG ALG
ALG %, where ALG represents analgorithm you evaluate and ALG is the smallest objective value across the set of all
algorithms you compare with (including your one). You are not expected to beat the
existing results (though it would be fantastic), but you should strive to achieve the best
possible solutions.
Analyse the performance of your approach. Try to identify the classes of instances where
it seems superior and think about factors that a ect its behaviour. Build a series of
diagrams which illustrate the dependence of solution quality on the problem size and class.
Similarly, draw diagrams to express the increase of the running time as the problem size
increases. Find out whether your approach runs faster for a certain class of the instances.
Finally, summarise your ndings and discuss the pros and cons of your algorithm that
you may think about.
Exercise 6 Testing your solutions (worth of 20%)
Submit your best solution as a text le for each of the test instances. The format of
the text le and submission instructions are provided below. In addition, submit you
program code. Your code will be manually checked for whether it performs the same
algorithmic approach as you report. Therefore, provide some high level comments for
your methods and classes along with comments for important parts of your code. You
will not get any marks for style. and commenting, but we should be able to verify that
your approach matches your code. Your solution les will be tested automatically by a
marking script. to verify their feasibility.
5
COMP SCI 2203 - Problem Solving Software Development Semester 2, 2017
4 Input File Format
2L-CVRP test instances.zip is a zip archive le available on the CANVAS web-page of
the assignment. It stores 180 test instances for the 2L-CVRP problem as text les of the
following structure.
Instance: ***
Class: ***
*** --- number of customers (excluding the depot)
*** --- number of vehicles
*** --- number of items
Capacity - length - width of vehicles
*** *** ***
Node - x - y - total weight of the demand
0 *** *** ***
1 *** *** ***
...
Node - number of items - l - w for each item
0 0
1 *** *** *** *** ***
...
Each instance le is a series of records structured as lines of text. There are ve di erent
sections to specify the name of an instance, its class along with details on the number
of customers, vehicles, and items, followed by the sections containing parameters of the
vehicles, coordinates of the customers, and features of the items in demand. The parts
of each line are separated by one or more space characters.
Instance section declares the name of an instance.
Class section determines the problem’s class, an integer number between 1 and 5. The
class characterises the way of generation of the item set. In Class 1, with each customer
is associated a single item of width and length equal to 1. The problems of Class 1 are
in fact pure Capacitated Vehicle Routing Problem instances, as every customer sequence
is feasible in terms of the loading constraints of the problem. They are used to test the
algorithmic e ectiveness in terms of the routing aspect of the problem. In Classes 2-5,
for each customer i, a set of mi items has been generated. Each item is classi ed into one
of the three shape categories, namely vertical, homogeneous and horizontal, with equal
probability. The dimensions (width and length) of an item are uniformly distributed into
the ranges determined by this items shape category. To get more details on the instance
classes, you are referred to (Gendreau et al., 2008). Each class consists of 36 instances
containing from 15 to 255 customers and from 15 to 786 items. The rest of the Class
section details the number of customers (excluding the central depot), the number of
vehicles, and the total number of items.
Capacity section describes the capacity C, length L, and width W of the vehicles. L and
W of the loading surface are equal to 40 and 20 across all the test instances, respectively.
There is a guarantee that the provided eet is enough to transport all the items to
customers for both the unrestricted and the sequential versions of the problem. That is,
you are given enough vehicles of su cient capacity and size.
6
COMP SCI 2203 - Problem Solving Software Development Semester 2, 2017
Node (x, y, demand) section sequentially details the coordinates of each customer (and
the depot) along with the total weight of demanded items. Then the distance between
any two vertices is an Euclidean distance (no rounding).
Node (number of items, l, w) is the last section, which speci es the number of items
along with the length and the width of each item associated with a speci c customer.
The rst record refers to the depot, therefore has no items.
5 Solution File Format
Your algorithm must produce solution les of the following structure.
Instance: ***
Class: ***
Objective value: ***.**
Number of vehicles: ***
Routes:
0 index_i *** index_j 0
0 index_k *** *** index_l 0
...
Packing:
Node - number of items - h - w for each item
1 m_1 x_11 y_11 x_12 y_12 *** ***
2 m_2 x_21 y_21 x_22 y_22 ***
...
Instance and Class records must contain the name and the problem’s class as de ned
by the original input le, respectively. Objective value reports the cost of the solution,
which is a oating-point number rounded to two decimal places. Number of vehicles
records how many vehicles have been utilized in your solution in fact. Routes section
describes each of the routes computed by your algorithm. Each record must start and
end with 0; that is, every vehicle must depart from the depot and return back to it. All
other integers of the record correspond to customers assigned to the route. They must
appear in the order as visited by the vehicle. For example, the second integer represents
the city visited right after departure from the depot. All integers of the record must
be space delimited. Note that the total number of records here must be equal to the
number of vehicles used by the solution. Packing section considers nodes (customers)
in ascending order starting from the rst one. Each record speci es the index of a node,
the number of requested items, and the coordinates of each item as computed by your
algorithm. The coordinates must appear with respect to the front left corner of a vehicle
which sets the (0;0) point as depicted in Figure 1.
6 Submission instructions for programming code and
the report
You must submit your report in the PDF format and name the le as report.pdf. On
the rst page of the report, you must give a title and mention the names and IDs of