Cookies help us deliver our services. By using our services, you agree to our use of cookies.

Completed
48
Submissions
57
Participants
3522
Views

Overview

Version française disponible ici.

Deutsche Version hier erhältlich.

Red alert! Last night, burglars stole cheese stocks throughout the canton of Fribourg! Even immediate police intervention could not prevent this theft. Nevertheless, thanks to the close collaboration between the special units in Europe, you, a collaborator of the PMS (Possible Mission Service) have been able to locate the places where the thieves hide the cheese.

It turns out that they have stored it at different locations across Europe. These places are all protected by an alarm system that no human being can disable. But as a manager of new technologies within the PMS, you have recently developed a special drone that could disable this type of alarm.

For each location, a due time has been fixed by which we would like to recover the cheese stored in that location. Your mission is to program the drone to visit all storage locations exactly once and turn off the alarm such that the total delay is minimized. This will allow the special anti-thief-cheese units to recover the cheese as quickly as possible. The delay of a storage location is computed as follows: If the drone can deactivate the alarm before the due time of that location, then the delay is equal to 0; otherwise, the delay equals the difference between the time of arrival of the drone and the due time of the location. The total delay is then the sum of the delays of the different locations. Finally, the time it takes to arrive at a location is the total distance travelled from the point of departure to that location.

To understand the challenge you are facing consider the following small example:

In this example there are exactly four different storage locations. The position of each location is given by its x-coordinate and its y-coordinate. For example, the position of Location 4 is (3,4), i.e., its x-coordinate is 3 and its y-coordinate is 4. The distance between two locations is given by the Euclidean distance rounded to its closest integer. For example,

• The distance between Location 1 and Location 4 is the square-root of (3-0)*(3-0) + (4-0) * (4-0) rounded to the closest integer, which equals 5.
• The distance between Location 2 and Location 3 is the square-root of (-2-0)(-2-0) + (-2-7)(-2-7) rounded to the closest integer, which equals 9.

Suppose now that the locations have the following due times. Location 1: 2; Location 2: 3; Location 3: 8 and Location 4: 13. If, in the above example, you decide to program the drone to visit the locations in the order 1-2-3-4, then we have the following arrival times:

• Arrival time for Location 1: 0 = 0
• Arrival time for Location 2: 0 + 3 = 3
• Arrival time for Location 3: 0 + 3 + 9 = 12
• Arrival time for Location 4: 0 + 3 + 9 + 4 = 16

This would thus result in the following delays:

• Delay for Location 1: 0
• Delay for Location 2: 0
• Delay for Location 3: 12-8 =4
• Delay for Location 4: 16-13 = 3

So, the total delay is 7 if the locations are visited in the order 1-2-3-4.

Your goal is to find the order that minimizes the delay for two larger instances.

Format of datasets

There are two datasets “Swiss.txt” and “Large.txt” . They have the following format. One row per location consisting of four integers:

• ID: the identification number of the location (1 is the starting location)
• X-COORDINATE: the X-coordinate of the location
• Y-COORDINATE: the Y-coordinate of the location
• DUE-TIME: the due time of the location

So “Swiss.txt” consists of 30 rows and “Large.txt” consists of 1379 rows.

In addition we have prepared an Excel document where the cities of “Swiss.txt” are illustrated and the objective function is evaluated automatically for inserted solutions.

All the indicated documents are available under the item “Dataset” .

Submission format

The submission should be a text file consisting of one or two rows.

• The first row contains the solution to the Swiss instance: a permutation of the Location IDs 1, 2, …, 30 written with spaces between the IDs.
• The second row (if it exists) contains the solution of the Large instance: a permutation of the Location IDs from 1 to 1379 written with spaces between the IDs.

If no second row is given then a delay of 9999999999 is given to the Large instance.

An example of a submission can be found here.

Evaluation

Submissions are ranked by their delay (a smaller delay is better) of the submitted solutions to the Swiss challenge consisting of the 30 most populous cities of Switzerland.

Two submissions with the same delay on the Swiss challenge are then ranked according to

• the delay of their submissions to the large instance of 1379 locations.
• If the delay of the solutions to the large instance is also the same then the submissions are ranked according to the date of submission (the earlier the better).

Rules

Competition is only for students of Swiss High Schools.

Prizes

• CHF 500.- for first prize
• CHF 300.- for second prize
• CHF 200.- for third prize

Resources

The competition is organized by the Swiss Operations Research Society