# CSCE 782: Problem Set 4

## Due: Wednesday, 22 October 2003 @ midnight

Figure 1: Click on the image in order to see the applet and get the source code

## The Mailmen Problem

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

The mailman problem itself was popularized by

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 delivered. Upon `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:

• The total distance should be minimized.
• The total distance should decrease as we increase the number of mailmen. Notice (by clicking on `run-tests`) that my solution actually does the opposite!
• The total distance should increase sub-linearly as the number of letters is increased.

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.

### Submission Instructions

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:
email:
ID:

I understand that it is the responsibility of every member of the Carolina community to uphold an maintain the academic standards and integrity of the University of South Carolina. Any member of the University community, who has reasonable grounds to believe that an infraction of the Code of Student Academic Responsibility has occurred, has an obligation to report the alleged violation.

I certify that I have neither given nor received unauthorized aid on this problem set.

José M. Vidal