Generated on for Gecode by doxygen 1.17.0

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.

(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.

Definition at line 206 of file tsptw.cpp.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum

Search engines.

Enumerator
SEARCH_BAB 
SEARCH_ASTAR 
SEARCH_CABS 

Definition at line 222 of file tsptw.cpp.

Constructor & Destructor Documentation

◆ TSPTW() [1/2]

TSPTW::TSPTW ( const InstanceOptions & opt)
inline

The actual problem.

Definition at line 226 of file tsptw.cpp.

◆ TSPTW() [2/2]

TSPTW::TSPTW ( TSPTW & s)
inline

Constructor for cloning s.

Definition at line 330 of file tsptw.cpp.

Member Function Documentation

◆ cost()

virtual IntVar TSPTW::cost ( void ) const
inlinevirtual

Return cost.

Definition at line 275 of file tsptw.cpp.

◆ prefix()

int TSPTW::prefix ( void ) const
inline

Return the number of positions assigned from the start.

Definition at line 279 of file tsptw.cpp.

◆ visited()

void TSPTW::visited ( int k,
Support::BitSet< Region > & v ) const
inline

Store the customers in the first k positions in v.

Definition at line 286 of file tsptw.cpp.

◆ same_visited()

bool TSPTW::same_visited ( const TSPTW & s,
int k ) const
inline

Whether the first k positions of this and s visit the same customers.

Definition at line 291 of file tsptw.cpp.

◆ prefix_cost()

int TSPTW::prefix_cost ( int k) const
inline

Return the travel time of the first k (assigned) positions.

Definition at line 302 of file tsptw.cpp.

◆ dominates()

bool TSPTW::dominates ( const TSPTW & s) const
inline

Whether this partial tour dominates s.

Definition at line 309 of file tsptw.cpp.

◆ key()

std::size_t TSPTW::key ( void ) const
inline

Return a key for dominance.

Definition at line 316 of file tsptw.cpp.

◆ copy()

virtual Space * TSPTW::copy ( void )
inlinevirtual

Copy during cloning.

Definition at line 338 of file tsptw.cpp.

◆ print()

virtual void TSPTW::print ( std::ostream & os) const
inlinevirtual

Print solution.

Reimplemented from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > >.

Definition at line 342 of file tsptw.cpp.

◆ instance_spec

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.

◆ main()

int main ( int argc,
char * argv[] )
related

Main-function.

Definition at line 355 of file tsptw.cpp.

Member Data Documentation

◆ p

const Problem TSPTW::p
protected

The instance.

Definition at line 209 of file tsptw.cpp.

◆ x

IntVarArray TSPTW::x
protected

Customer at each position of the tour.

Definition at line 211 of file tsptw.cpp.

◆ pos

IntVarArray TSPTW::pos
protected

Position of each customer.

Definition at line 213 of file tsptw.cpp.

◆ c

IntVarArray TSPTW::c
protected

Travel time to each position, and back to the depot.

Definition at line 215 of file tsptw.cpp.

◆ t

IntVarArray TSPTW::t
protected

Start of service at each position.

Definition at line 217 of file tsptw.cpp.

◆ total

IntVar TSPTW::total
protected

Total travel time.

Definition at line 219 of file tsptw.cpp.


The documentation for this class was generated from the following file: