Description of the projectThis is project is the realisation of an assignment for :
<h2>Master IA of the universitat politècnica de catalunya (Barcelona, España)
assignatura de IA
Laboratory Assignment 1
September 22nd 2008
Satement of the assignment:
"The goal of this assignment is to use the java classes explained in the laboratory sessions to solve
the following local search problem.
The Barcelona city council has decided to start a service of car pooling to help reduce city trac
and CO2 emissions.
Each user in this service says how many available seats has in his car, his home address and his
work address. Each month it is the turn of a dierent group of users to provide the vehicles for car
pooling (we will suppose that all users have always three seats available). During that month people
that are sharing their car adapt their route to pick up other users and take them to work. During the
route the car could pick up more people than available seats if the routes of this people are disjoint.
We have a constraint about the routes that is that the driver of the car has to arrive to his work
on time, that limits the total length of the route. We will suppose that the mean speed of city trac
is 30 km/h, the car starts its route at 7 AM and the driver has to arrive at work before 8 AM.
To simplify the problem we will suppose that the city is a square of 1010 kilometers and
the streets are a grid where each block is 100100 meters. The addresses of the users and their
destinations correspond to intersections of the grid. The distance between two points inside the city
will be calculated as:
d(i; j) = jix jxj + jiy jyj
Where ix and iy are the coordinates x and y of the i point of the grid.
We need to obtain the solution for this problem for a given month, we want a plan that for each
person that shares his car that month has a route that allows to pick up and take to their work a set
of users respecting the number of available seats in the car and the other constraints. Keep in mind
that a solution has to take everybody to their work. The main goal is to minimize the total length
of the routes of the cars.
Implement the classes needed to solve the problem using the AIMA classes seen in the labora-
tory sessions. Produce a report of the work which includes the source code of these classes.
The implementation has to be able to generate dierent randomly generated problems that
allow the change the following parameters:
The number of users that share their car and the number of users to be picked up.
The spatial distribution of the home address of the drivers (uniform, clustered in one part
of the city, clustered in some parts of the city). The rest of addresses should be random.
Experiment with dierent strategies (two at least) to generate the initial state. The problem
may have to start from a state that is not a solution.
Choose and test dierent sets of search operators.
Experiment with two heuristic functions:
A function that minimizes the total length of the routes
A function that minimizes the total length of the routes but prioritizes that all routes are
approximately the same length
If the search initiates from a state that is not a solution you will have to think about what is
necessary to add to the heusitic functions to guide the search to the solutions space
Design a set of experiments for each algorithm (Hill Climbing and Simulated Annealing) to
answer the following questions:
Given a total number of users What proportion between drivers and users to be picked up
gives the better solutions? Is this proportion the same if the number of users is changed?
Think that there will be proportions that will not give any solution.
Does the distribution of the cars inside the city have any inuence in the quality of the
Is there a signicative dierence among the solutions obtained using the two heuristic
In order to answer this questions you have rst to nd out what strategy of initialization is
better and the most suitable set of search operators. To do this you have to choose a specic
scenario and perform some experiments. You have to decide what values to use for the dierent
parameters of the problem in the experiments and to give a justication of your decisions.
In the case of the Simulated Annealing algorithm, explore also the eect of dierent values for
Explain and justify all the decisions that you make. The conclusions must include:
Comments about the results of each experiment. Explain what you expected and what hap-
Comparison of the two local search algorithms using the results of the experiments (quality
of the solutions and execution time).
It is essential to be systematic in the experimentation process, do not make your decisions ran-
domly. Use the results of each experiment to guide your decisions. Statistics and graphics could be
a good way to support your conclusions.
The grade will depend on the quality of the experiments performed, the quality of the comments
and conclusions and the quality of the written report.
This assignment has to be solved preferably by teams of two students.
The report and the code are due by November 3rd by 5 PM. The deliver will be by email to
It is important to plan the development of this assignment and do not do all the work at the last