59 const int PA_d[PA_n*PA_n] = {
60 0,0,0,0,0,0,0,0,0,0,0,
61 71,0,85,85,85,96,85,85,97,85,77,
62 50,65,0,77,77,62,77,77,62,77,74,
63 64,74,88,0,88,80,88,88,82,88,87,
64 44,54,68,68,0,60,68,68,62,68,67,
65 51,75,51,51,51,0,51,51,80,51,65,
66 53,64,78,78,78,68,0,78,69,78,76,
67 51,67,69,69,69,75,69,0,75,69,63,
68 43,61,71,71,71,43,71,71,0,71,68,
69 53,64,78,78,78,68,78,78,69,0,80,
70 42,66,52,52,52,70,52,52,70,52,0
72 const int PA_w[2*PA_n] = {
73 0,9396, 0,865, 399,1299, 550,1450, 685,1585, 819,1719,
74 1208,2108, 1412,2312, 1701,2330, 2413,3313, 3798,4698
79 const int PB_d[PB_n*PB_n] = {
80 0,19,17,34,7,20,10,17,28,15,23,29,23,29,21,20,9,16,21,13,12,
81 19,0,10,41,26,3,27,25,15,17,17,14,18,48,17,6,21,14,17,13,31,
82 17,10,0,47,23,13,26,15,25,22,26,24,27,44,7,5,23,21,25,18,29,
83 34,41,47,0,36,39,25,51,36,24,27,38,25,44,54,45,25,28,26,28,27,
84 7,26,23,36,0,27,11,17,35,22,30,36,30,22,25,26,14,23,28,20,10,
85 20,3,13,39,27,0,26,27,12,15,14,11,15,49,20,9,20,11,14,11,30,
86 10,27,26,25,11,26,0,26,31,14,23,32,22,25,31,28,6,17,21,15,4,
87 17,25,15,51,17,27,26,0,39,31,38,38,38,34,13,20,26,31,36,28,27,
88 28,15,25,36,35,12,31,39,0,17,9,2,11,56,32,21,24,13,11,15,35,
89 15,17,22,24,22,15,14,31,17,0,9,18,8,39,29,21,8,4,7,4,18,
90 23,17,26,27,30,14,23,38,9,9,0,11,2,48,33,23,17,7,2,10,27,
91 29,14,24,38,36,11,32,38,2,18,11,0,13,57,31,20,25,14,13,17,36,
92 23,18,27,25,30,15,22,38,11,8,2,13,0,47,34,24,16,7,2,10,26,
93 29,48,44,44,22,49,25,34,56,39,48,57,47,0,46,48,31,42,46,40,21,
94 21,17,7,54,25,20,31,13,32,29,33,31,34,46,0,11,29,28,32,25,33,
95 20,6,5,45,26,9,28,20,21,21,23,20,24,48,11,0,23,19,22,17,32,
96 9,21,23,25,14,20,6,26,24,8,17,25,16,31,29,23,0,11,15,9,10,
97 16,14,21,28,23,11,17,31,13,4,7,14,7,42,28,19,11,0,5,3,21,
98 21,17,25,26,28,14,21,36,11,7,2,13,2,46,32,22,15,5,0,8,25,
99 13,13,18,28,20,11,15,28,15,4,10,17,10,40,25,17,9,3,8,0,19,
100 12,31,29,27,10,30,4,27,35,18,27,36,26,21,33,32,10,21,25,19,0
102 const int PB_w[2*PB_n] = {
103 0,408, 62,68, 181,205, 306,324, 214,217, 51,61,
104 102,129, 175,186, 250,263, 3,23, 21,49, 79,90,
105 78,96, 140,154, 354,386, 42,63, 2,13, 24,42,
110 const Builtin instances[] = {
115 const unsigned int n_instances =
sizeof(instances)/
sizeof(Builtin);
130dist[n][n]: 0..gecode.int_max / 2 / n
132type time = 0..gecode.int_max / 2
139check node.ready <= node.due "the time window of a node is invalid"
140check nodes[0].ready == 0 "the depot (node 0) must open at time 0"
160 if (opt.builtin(b)) {
161 if (b >= n_instances)
166 }
else if (opt.is_file()) {
169 int m =
static_cast<int>(data.
integer(
"n"));
172 for (
int i=0; i<m; i++) {
173 win[2*i] = ready[i]; win[2*i+1] = due[i];
181 bool valid(
void)
const {
228 x(*this,
p.n-1,1,
p.n-1),
pos(*this,
p.n-1,0,
p.n-2),
232 IntArgs d(n*n), from(n), to(n), ready(n), due(n);
233 for (
int i=0; i<n*n; i++)
235 for (
int i=0; i<n; i++) {
236 from[i] =
p.d[i]; to[i] =
p.d[i*n];
237 ready[i] =
p.w[2*i]; due[i] =
p.w[2*i+1];
243 for (
int k=1; k<n; k++)
244 for (
int i=0; i<n; i++)
245 for (
int j=0; j<n; j++)
246 s[i*n+j] = std::min(s[i*n+j], s[i*n+k]+s[k*n+j]);
248 for (
int j=1; j<n; j++)
249 for (
int k=1; k<n; k++)
250 if ((j != k) && (ready[k] + s[k*n+j] > due[j]))
256 for (
int j=1; j<n; j++)
257 for (
int k=1; k<n; k++)
259 legs.
add({j, k, d[j*n+k]});
261 for (
int i=1; i<n-1; i++) {
265 for (
int i=0; i<n-1; i++)
268 rel(*
this,
t[n-2] +
c[n-1] <= due[0]);
287 for (
int i=0; i<k; i++)
288 v.
set(
static_cast<unsigned int>(
x[i].val()));
296 for (
int i=0; i<k; i++)
297 if (!v.
get(
static_cast<unsigned int>(s.
x[i].val())))
304 for (
int i=0; i<k; i++)
311 if ((k == 0) || (k != s.
prefix()) || (
x[k-1].val() != s.
x[k-1].val()))
316 std::size_t
key(
void)
const {
319 unsigned int n =
static_cast<unsigned int>(
p.n);
324 for (
unsigned int i = v.
next(0); i < n; i = v.
next(i+1))
339 return new TSPTW(*
this);
342 virtual void print(std::ostream& os)
const {
344 for (
int i=0; i<
x.
size(); i++)
345 os <<
" -> " <<
x[i];
346 os <<
" -> 0" << std::endl
347 <<
"\tTravel time: " <<
total << std::endl;
361#ifdef GECODE_HAS_EXPERIMENTAL
365 opt.
parse(argc,argv);
369 std::cerr <<
"Error: instance must be a number between 0 and " << n_instances-1 <<
" or a file" << std::endl;
373 std::cerr << e.
what() << std::endl;
376 switch (opt.search()) {
380#ifdef GECODE_HAS_EXPERIMENTAL
385 [](
const Space& s) -> std::int64_t {
386 return static_cast<const TSPTW&
>(s).
cost().min();
389 return static_cast<const TSPTW&
>(a)
392 g.dominance_key = [](
const Space& s) {
393 return static_cast<const TSPTW&
>(s).
key();
static void run(const Options &opt, Script *s=nullptr)
Options for scripts with additional instance parameter
Named values read from an instance.
IntArgs ints(const std::string &n, const IntArgs &path=IntArgs()) const
Return all integers in the array or row n at path.
long long int integer(const std::string &n, const IntArgs &path=IntArgs()) const
Return the integer n at path.
Exception for errors in specs and instance files
virtual const char * what(void) const noexcept override
Return the full message.
Passing integer arguments.
IntArgs(void)
Allocate empty array.
IntVarArgs(void)
Allocate empty array.
Guidance for heuristic search engines (experimental).
std::function< bool(const Space &, const Space &)> dominates
Whether the first space dominates the second (optional).
bool get(unsigned int i) const
Access value at bit i.
void set(unsigned int i)
Set bit i.
unsigned int next(unsigned int i) const
Return position greater or equal i of next set bit (i is allowed to be equal to size).
Class representing a set of tuples.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
void finalize(void)
Finalize tuple set with dense support data.
bool assigned(void) const
Test if all variables are assigned.
int size(void) const
Return size of array (number of elements).
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
std::size_t key(void) const
Return a key for dominance.
int main(int argc, char *argv[])
Main-function.
IntVar total
Total travel time.
const Problem p
The instance.
const char * instance_spec
Reader spec for TSPTW files.
int prefix(void) const
Return the number of positions assigned from the start.
virtual Space * copy(void)
Copy during cloning.
bool dominates(const TSPTW &s) const
Whether this partial tour dominates s.
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.
virtual void print(std::ostream &os) const
Print solution.
IntVarArray c
Travel time to each position, and back to the depot.
virtual IntVar cost(void) const
Return cost.
TSPTW(TSPTW &s)
Constructor for cloning s.
IntVarArray t
Start of service at each position.
IntVarArray pos
Position of each customer.
int prefix_cost(int k) const
Return the travel time of the first k (assigned) positions.
TSPTW(const InstanceOptions &opt)
The actual problem.
IntVarArray x
Customer at each position of the tour.
void parse(int argc, char *argv[])
Parse commandline arguments.
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
Gecode toplevel namespace
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
void cmb_hash(std::size_t &seed, const T h)
Combine hash value h into seed.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .