Example: Travelling salesperson with time windows More...
Public Types | |
| enum | { SEARCH_BAB , SEARCH_ASTAR , SEARCH_CABS } |
| Search engines. More... | |
Public Member Functions | |
| 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. | |
| Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > | |
| 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. | |
| Public Member Functions inherited from Gecode::Driver::IgnoreStepOption< BaseSpace > | |
| IgnoreStepOption (const Options &) | |
| Constructor. | |
| IgnoreStepOption (BaseSpace &e) | |
| Constructor used for cloning. | |
Protected Attributes | |
| const Problem | p |
| The instance. | |
| IntVarArray | x |
| Customer at each position of the tour. | |
| IntVarArray | pos |
| Position of each customer. | |
| IntVarArray | c |
| Travel time to each position, and back to the depot. | |
| IntVarArray | t |
| Start of service at each position. | |
| IntVar | total |
| Total travel time. | |
Related Symbols | |
(Note that these are not member symbols.) | |
| const char * | instance_spec |
| Reader spec for TSPTW files. | |
| int | main (int argc, char *argv[]) |
| Main-function. | |
Additional Inherited Members | |
| Static Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > | |
| static std::ostream & | select_ostream (const char *sn, std::ofstream &ofs) |
| Choose output stream according to sn. | |
| static void | run (const Options &opt, Script *s=nullptr) |
Detailed Description
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.
Member Enumeration Documentation
◆ anonymous enum
| anonymous enum |
Constructor & Destructor Documentation
◆ TSPTW() [1/2]
|
inline |
◆ TSPTW() [2/2]
|
inline |
Member Function Documentation
◆ cost()
|
inlinevirtual |
◆ prefix()
|
inline |
◆ visited()
|
inline |
◆ same_visited()
|
inline |
◆ prefix_cost()
|
inline |
◆ dominates()
|
inline |
◆ key()
|
inline |
◆ copy()
|
inlinevirtual |
◆ print()
|
inlinevirtual |
Print solution.
Reimplemented from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > >.
Friends And Related Symbol Documentation
◆ instance_spec
|
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.
◆ main()
Member Data Documentation
◆ p
◆ x
|
protected |
◆ pos
|
protected |
◆ c
|
protected |
◆ t
|
protected |
◆ total
The documentation for this class was generated from the following file:
- examples/tsptw.cpp
