|
| | TSPTW (const InstanceOptions &opt) |
| | The actual problem.
|
| virtual IntVar | cost (void) const |
| | Return cost.
|
| int | prefix (void) const |
| | Return the number of positions assigned from the start.
|
| void | visited (int k, Support::BitSet< Region > &v) const |
| | Store the customers in the first k positions in v.
|
| bool | same_visited (const TSPTW &s, int k) const |
| | Whether the first k positions of this and s visit the same customers.
|
| int | prefix_cost (int k) const |
| | Return the travel time of the first k (assigned) positions.
|
| bool | dominates (const TSPTW &s) const |
| | Whether this partial tour dominates s.
|
| std::size_t | key (void) const |
| | Return a key for dominance.
|
| | TSPTW (TSPTW &s) |
| | Constructor for cloning s.
|
| virtual Space * | copy (void) |
| | Copy during cloning.
|
| virtual void | print (std::ostream &os) const |
| | Print solution.
|
| | ScriptBase (const Options &opt) |
| | Constructor.
|
| | ScriptBase (ScriptBase &e) |
| | Constructor used for cloning.
|
| virtual void | compare (const Space &home, std::ostream &os) const |
| | Compare with s.
|
| | IgnoreStepOption (const Options &) |
| | Constructor.
|
| | IgnoreStepOption (BaseSpace &e) |
| | Constructor used for cloning.
|
Example: Travelling salesperson with time windows
Starting and ending at the depot, visit every customer once such that service at each customer starts within its time window (waiting is allowed). Minimize the total travel time. The instances are from López-Ibáñez and Blum's collection. The instance is either the number of a built-in instance or a file from that collection.
The tour is built from the depot one customer at a time. With the experimental heuristic search engines, the minimal total travel time is the bound. CABS also uses dominance: a partial tour dominates another if it has visited the same customers, ends at the same customer, and is neither later nor more expensive.
Definition at line 206 of file tsptw.cpp.
| const char* instance_spec |
|
related |
Initial value: = R"(format tsptw
comment "#"
n: 2..1000
dist[n][n]: 0..gecode.int_max / 2 / n
type time = 0..gecode.int_max / 2
repeat n as nodes {
each node
ready: time
due: time
}
check node.ready <= node.due "the time window of a node is invalid"
check nodes[0].ready == 0 "the depot (node 0) must open at time 0"
)"
Reader spec for TSPTW files.
The format of López-Ibáñez and Blum's collection: the number of nodes (including the depot), the travel time matrix, and the ready and due time of each node. See Instance::Spec for the spec language.
Definition at line 126 of file tsptw.cpp.