VRPTWController

VRPTWController is used to run and calculate score for the 12th DIMACS Implementation Challenge: VRPTW track. Specified in Competition Rules.

Installation

Linux, MacOS & OpenBSD:

git clone https://github.com/laser-ufpb/VRPTWController
cd VRPTWController
mkdir build
cd build
cmake ..
make

Testing the Controller with a dummy solver:

make test

The output will be at build/ as DIMACS-VRPTW-Dummy-R108.out.

Usage example

How to run:

./VRPTWController <Competitor ID> <Instance path> <CPU mark> <Time limit> <Instance BKS> <If BKS is optimal [0/1]> <Path to solver>

Example:

./VRPTWController Wolverine R108.txt 2064 1800 932.1 1 Solver1

How to run the instances:

Generating the script:

sh genScript1.sh <Competitor ID> <CPU mark> <Solver path> > VRPTW-Script1.sh

Running the instances:

sh VRPTW-Script1.sh

to run all the instances, you also have to run the scripts genScript2.sh and genScript3.sh.

Example:

sh genScript1.sh Wolverine 2064 Solver1 > VRPTW-Script1.sh
sh VRPTW-Script1.sh

For more examples and usage, please refer to the Competition Rules.

How to call the solver indirectly via shell script

Suppose a file named solver has the following content:

#!/usr/bin/env bash
./real-solver $1 $2

Therefore, you can use solver (after calling chmod +x solver) instead of the original executable file real-solver (which could have other command-line arguments in addition to the two defined in the challenge rules).

where is the bug

The rule says that Matrix D containing the distances and times is obtained from the location coordinates, by computing the Euclidean distances truncated to one decimal place.
However, the program fails to contain the precise number after conversion to binary internally (e.g. 0.1-->0.000110011). As a result, it's very dangerous if you use C++ to compare two real numbers directly. The core VRPTWController code is as follows.

travelTime = max(travelTime + edgeCost + (double) instance->s[route.at(i - 1)], (double) instance->l[route.at(i)]);
// std::cout << "("<< route.at(i - 1) << "," << route.at(i) << ") c" << edgeCost << " t" << travelTime << std::endl;
if(travelTime > instance->u[route.at(i)]) { // checks TW violation
    std::cout << "TW of " << route.at(i) << " ([" << instance->l[route.at(i)] 
        << "," << instance->u[route.at(i)] << "]) was violated (arrival time = " << travelTime << ")" << std::endl;
    return false;
}

And now I give a specific case that is wrongly judged by this code. In instance Homberger/C1_2_8.TXT, my algorithm produces a valid route [0, 155, 78, 175, 119, 166, 35, 126, 71, 9, 1, 99, 53, 0] but is warning by the message TW of 126 ([399,609]) was violated (arrival time = 609). Then I checked each step in this route:

155 ( 14, 272, 90)   dis: (14.7648230602, 14.7)   arrive:  (14.7000000000000, 14.7)    after service: (104.7000000000000, 104.7)
 78 ( 53, 350, 90)   dis: ( 1.4142135624,  1.4)   arrive: (106.1000000000000, 106.1)   after service: (196.1000000000000, 196.1)
175 (168, 422, 90)   dis: ( 4.1231056256,  4.1)   arrive: (200.2000000000000, 200.2)   after service: (290.2000000000000, 290.2)
119 (107, 341, 90)   dis: (38.5875627631, 38.5)   arrive: (328.7000000000000, 328.7)   after service: (418.7000000000000, 418.7)
166 (177, 456, 90)   dis: ( 3.1622776602,  3.1)   arrive: (421.8000000000001, 421.8)   after service: (511.8000000000001, 511.8)
 35 (289, 531, 90)   dis: ( 3.6055512755,  3.6)   arrive: (515.4000000000001, 515.4)   after service: (605.4000000000001, 605.4)
126 (399, 609, 90)   dis: ( 3.6055512755,  3.6)   arrive: (609.0000000000001, 609.0)   after service: (699.0000000000001, 699.0)

The first number in arrive/after service is calculated by direct double operations in C++, similar to VRPTWController (print 13 digits after the decimal point). The second number in arrive/after service is the precise number. It's clear that the judge mistakenly thinks that the arrival time at 126 is 609.0000000000001 which is larger than the limitation 609.

suggestions to fix the problem

One simple but risky way is: add a traditional EPS trick in the code. i.e., replace the code if(travelTime > instance->u[route.at(i)]) with if(travelTime > instance->u[route.at(i)]) + EPS. Arbitrary setting in this problem (e.g. EPS=1e-9 or EPS=1e-6) is enough to fix the bug, because all the real numbers only have one digit after the decimal point.
There is another way that can fix this bug completely with more modification. This VRPTWController can always contain integers instead of real numbers. i.e., multiply each number by 10, and use integer comparison everywhere.

laser-ufpb / vrptwcontroller Goto Github PK