For this problem set you will implement a solution to the famous mailman problem. The mailman problem is an instance of the task allocation problem which is discussed in
Figure 1 shows the netlogo implementation I'm providing. The
triangles are the turtles, the white squares are the letters to
be delivered, and the yellow circles are letters that have been
setup the mailmen and letters are
randomly placed on the screen. Each letter is assigned a pair of
delivery coordinates. The job of the mailman is to move the
letters from their current position to the position specified by
their delivery coordinates. In doing so the mailman should also
try to minimize the total distance that they travel.
A little thinking about this problem should quickly lead you to conclude that there is an obvious algorithm for calculting the optimal allocation of letters to mailmen. And, this algorithm amounts to solving an exponential number of travelling-salesman problems, each of which is NP-complete. As such, we can quickly conclude that the optimal allocation, especially for 100 letters, is beyond our computational capabilities.
The solution you will provide will, therefore, be only an approximation to the optimal. I will look for the following qualities in your solution:
run-tests) that my solution actually does the opposite!
Note also that in this implementation, unlike our previous ones,
each click of the
update button results in agents
moving different distances. This behavior is fine since the
agents record how much they have travelled.
This problem set is to be done individually. You cannot ask or receive help from anyone. As will all the problem sets, you will hand them in using our department's dropbox. For the netlogo problem sets you will hand in only one file, your .nlogo file. You will use the information tab of the program for writing your detailed explanation of the techniques you used, how the program works, how to set the controls to obtain the different behaviors you want to show, etc. The information tab needs to start with:Name: