Generated on for Gecode by doxygen 1.17.0
tsptw.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36#include <gecode/minimodel.hh>
37
38#include <algorithm>
39#include <string>
40
41using namespace Gecode;
42
44namespace {
45
47 class Builtin {
48 public:
50 int n;
52 const int* d;
54 const int* w;
55 };
56
58 const int PA_n = 11;
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
71 };
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
75 };
76
78 const int PB_n = 21;
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
101 };
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,
106 20,33, 9,21, 275,300
107 };
108
110 const Builtin instances[] = {
111 {PA_n, PA_d, PA_w},
112 {PB_n, PB_d, PB_w}
113 };
115 const unsigned int n_instances = sizeof(instances)/sizeof(Builtin);
116
126 const char* instance_spec = R"(format tsptw
127
128comment "#"
129n: 2..1000
130dist[n][n]: 0..gecode.int_max / 2 / n
131
132type time = 0..gecode.int_max / 2
133repeat n as nodes {
134 each node
135 ready: time
136 due: time
137}
138
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"
141)";
142
144 class Problem {
145 public:
147 int n;
158 Problem(const InstanceOptions& opt) : n(0) {
159 unsigned int b;
160 if (opt.builtin(b)) {
161 if (b >= n_instances)
162 return;
163 n = instances[b].n;
164 d = IntSharedArray(IntArgs(n*n, instances[b].d));
165 w = IntSharedArray(IntArgs(2*n, instances[b].w));
166 } else if (opt.is_file()) {
167 // The spec has checked the data
168 Instance::Data data = opt.data();
169 int m = static_cast<int>(data.integer("n"));
170 IntArgs ready = data.ints("ready"), due = data.ints("due");
171 IntArgs win(2*m);
172 for (int i=0; i<m; i++) {
173 win[2*i] = ready[i]; win[2*i+1] = due[i];
174 }
175 d = IntSharedArray(data.ints("dist"));
176 w = IntSharedArray(win);
177 n = m;
178 }
179 }
181 bool valid(void) const {
182 return n > 0;
183 }
184 };
185
186}
187
206class TSPTW : public IntMinimizeScript {
207protected:
209 const Problem p;
220public:
222 enum {
224 };
227 : IntMinimizeScript(opt), p(opt),
228 x(*this,p.n-1,1,p.n-1), pos(*this,p.n-1,0,p.n-2),
229 c(*this,p.n,0,Int::Limits::max),
230 t(*this,p.n-1,0,p.w[1]), total(*this,0,Int::Limits::max) {
231 int n = p.n;
232 IntArgs d(n*n), from(n), to(n), ready(n), due(n);
233 for (int i=0; i<n*n; i++)
234 d[i] = p.d[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];
238 }
239 channel(*this, x, 1, pos, 0, opt.ipl());
240 // Shortest travel times between customers (not via the depot), as
241 // the travel times need not be metric
242 IntArgs s(d);
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]);
247 // Customer j precedes k if j cannot be served after k
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]))
251 rel(*this, pos[j-1] < pos[k-1]);
252 element(*this, from, x[0], c[0]);
253 rel(*this, t[0] == max(element(ready,x[0]), c[0]));
254 // Travel time between consecutive customers
255 TupleSet legs(3);
256 for (int j=1; j<n; j++)
257 for (int k=1; k<n; k++)
258 if (j != k)
259 legs.add({j, k, d[j*n+k]});
260 legs.finalize();
261 for (int i=1; i<n-1; i++) {
262 extensional(*this, IntVarArgs({x[i-1], x[i], c[i]}), legs);
263 rel(*this, t[i] == max(element(ready,x[i]), t[i-1]+c[i]));
264 }
265 for (int i=0; i<n-1; i++)
266 rel(*this, t[i] <= element(due,x[i]));
267 element(*this, to, x[n-2], c[n-1]);
268 rel(*this, t[n-2] + c[n-1] <= due[0]);
269 linear(*this, c, IRT_EQ, total);
270 // Assign the next customer on every alternative: CABS prefix dominance
271 // does not account for value exclusions on the unassigned suffix.
272 branch(*this, x, INT_VAR_NONE(), INT_VALUES_MIN());
273 }
274
275 virtual IntVar cost(void) const {
276 return total;
277 }
278
279 int prefix(void) const {
280 int k = 0;
281 while ((k < x.size()) && x[k].assigned())
282 k++;
283 return k;
284 }
285
286 void visited(int k, Support::BitSet<Region>& v) const {
287 for (int i=0; i<k; i++)
288 v.set(static_cast<unsigned int>(x[i].val()));
289 }
290
291 bool same_visited(const TSPTW& s, int k) const {
292 Region r;
293 Support::BitSet<Region> v(r, static_cast<unsigned int>(p.n));
294 visited(k, v);
295 // Both prefixes visit k different customers, so inclusion is equality
296 for (int i=0; i<k; i++)
297 if (!v.get(static_cast<unsigned int>(s.x[i].val())))
298 return false;
299 return true;
300 }
301
302 int prefix_cost(int k) const {
303 int s = 0;
304 for (int i=0; i<k; i++)
305 s += c[i].val();
306 return s;
307 }
308
309 bool dominates(const TSPTW& s) const {
310 int k = prefix();
311 if ((k == 0) || (k != s.prefix()) || (x[k-1].val() != s.x[k-1].val()))
312 return false;
313 return (t[k-1].val() <= s.t[k-1].val()) && (prefix_cost(k) <= s.prefix_cost(k)) && same_visited(s, k);
314 }
315
316 std::size_t key(void) const {
317 int k = prefix();
318 Region r;
319 unsigned int n = static_cast<unsigned int>(p.n);
321 visited(k, v);
322 // The customers in increasing order, so that equal sets hash equally
323 std::size_t h = 0;
324 for (unsigned int i = v.next(0); i < n; i = v.next(i+1))
325 cmb_hash(h, i);
326 cmb_hash(h, k > 0 ? x[k-1].val() : 0);
327 return h;
328 }
329
331 x.update(*this, s.x);
332 pos.update(*this, s.pos);
333 c.update(*this, s.c);
334 t.update(*this, s.t);
335 total.update(*this, s.total);
336 }
337
338 virtual Space* copy(void) {
339 return new TSPTW(*this);
340 }
341
342 virtual void print(std::ostream& os) const {
343 os << "\tTour: 0";
344 for (int i=0; i<x.size(); i++)
345 os << " -> " << x[i];
346 os << " -> 0" << std::endl
347 << "\tTravel time: " << total << std::endl;
348 }
349};
350
354int
355main(int argc, char* argv[]) {
356 InstanceOptions opt("TSPTW", instance_spec);
357 opt.instance("0");
358 opt.solutions(0);
359 opt.search(TSPTW::SEARCH_BAB);
360 opt.search(TSPTW::SEARCH_BAB, "bab", "branch and bound");
361#ifdef GECODE_HAS_EXPERIMENTAL
362 opt.search(TSPTW::SEARCH_ASTAR, "astar", "A*");
363 opt.search(TSPTW::SEARCH_CABS, "cabs", "complete anytime beam search");
364#endif
365 opt.parse(argc,argv);
366 try {
367 Problem p(opt);
368 if (!p.valid()) {
369 std::cerr << "Error: instance must be a number between 0 and " << n_instances-1 << " or a file" << std::endl;
370 return 1;
371 }
372 } catch (const Instance::Error& e) {
373 std::cerr << e.what() << std::endl;
374 return 1;
375 }
376 switch (opt.search()) {
379 break;
380#ifdef GECODE_HAS_EXPERIMENTAL
383 {
385 [](const Space& s) -> std::int64_t {
386 return static_cast<const TSPTW&>(s).cost().min();
387 });
388 g.dominates = [](const Space& a, const Space& b) {
389 return static_cast<const TSPTW&>(a)
390 .dominates(static_cast<const TSPTW&>(b));
391 };
392 g.dominance_key = [](const Space& s) {
393 return static_cast<const TSPTW&>(s).key();
394 };
395 opt.guidance(&g);
396 if (opt.search() == TSPTW::SEARCH_ASTAR)
398 else
400 }
401 break;
402#endif
403 }
404 return 0;
405}
406
407// STATISTICS: example-any
static void run(const Options &opt, Script *s=nullptr)
Options for scripts with additional instance parameter
Definition driver.hh:834
Named values read from an instance.
Definition instance.hh:406
IntArgs ints(const std::string &n, const IntArgs &path=IntArgs()) const
Return all integers in the array or row n at path.
Definition data.cpp:405
long long int integer(const std::string &n, const IntArgs &path=IntArgs()) const
Return the integer n at path.
Definition data.cpp:390
Exception for errors in specs and instance files
Definition instance.hh:337
virtual const char * what(void) const noexcept override
Return the full message.
Definition data.cpp:56
Passing integer arguments.
Definition int.hh:653
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
Handle to region.
Definition region.hpp:55
Guidance for heuristic search engines (experimental).
Definition search.hh:1259
std::function< bool(const Space &, const Space &)> dominates
Whether the first space dominates the second (optional).
Definition search.hh:1272
Computation spaces.
Definition core.hpp:1787
Simple bitsets.
Definition bitset.hpp:45
Class representing a set of tuples.
Definition int.hh:2821
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
void finalize(void)
Finalize tuple set with dense support data.
std::size_t key(void) const
Return a key for dominance.
Definition tsptw.cpp:316
int main(int argc, char *argv[])
Main-function.
Definition tsptw.cpp:355
IntVar total
Total travel time.
Definition tsptw.cpp:219
const Problem p
The instance.
Definition tsptw.cpp:209
const char * instance_spec
Reader spec for TSPTW files.
Definition tsptw.cpp:126
int prefix(void) const
Return the number of positions assigned from the start.
Definition tsptw.cpp:279
virtual Space * copy(void)
Copy during cloning.
Definition tsptw.cpp:338
bool dominates(const TSPTW &s) const
Whether this partial tour dominates s.
Definition tsptw.cpp:309
void visited(int k, Support::BitSet< Region > &v) const
Store the customers in the first k positions in v.
Definition tsptw.cpp:286
@ SEARCH_CABS
Definition tsptw.cpp:223
@ SEARCH_ASTAR
Definition tsptw.cpp:223
@ SEARCH_BAB
Definition tsptw.cpp:223
bool same_visited(const TSPTW &s, int k) const
Whether the first k positions of this and s visit the same customers.
Definition tsptw.cpp:291
virtual void print(std::ostream &os) const
Print solution.
Definition tsptw.cpp:342
IntVarArray c
Travel time to each position, and back to the depot.
Definition tsptw.cpp:215
virtual IntVar cost(void) const
Return cost.
Definition tsptw.cpp:275
TSPTW(TSPTW &s)
Constructor for cloning s.
Definition tsptw.cpp:330
IntVarArray t
Start of service at each position.
Definition tsptw.cpp:217
IntVarArray pos
Position of each customer.
Definition tsptw.cpp:213
int prefix_cost(int k) const
Return the travel time of the first k (assigned) positions.
Definition tsptw.cpp:302
TSPTW(const InstanceOptions &opt)
The actual problem.
Definition tsptw.cpp:226
IntVarArray x
Customer at each position of the tour.
Definition tsptw.cpp:211
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:177
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
Definition driver.hh:1009
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.
Definition branch.cpp:39
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
Numerical limits for integer variables.
Definition int.hh:119
Finite domain integers.
Definition lastval.hh:52
Gecode toplevel namespace
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Definition int.hh:1813
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition val.hpp:100
void cmb_hash(std::size_t &seed, const T h)
Combine hash value h into seed.
Definition hash.hpp:44
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Case instances("Read::Instances", [](void) { const char *spec="comment \"+++\"\n" "instances {\n" " sections skip other {\n" " \"instance {name:word}\" optional\n" " \"{n:int}\" last { x[n]: int }\n" " }\n" "}\n";const char *text="header text\ninstance a\n2\n1 2\n+++\n" "instance b\ndescription\n1\n7\n+++ end\n";Params by_name, by_number, bad;by_name.set("instance", "b");by_number.set("instance", "1");bad.set("instance", "3");CHECK(equal(read(spec, text, by_name).ints("x"), {7}));CHECK(equal(read(spec, text, by_number).ints("x"), {1, 2}));CHECK(read(spec, text, by_number).text("name")=="a");CHECK(fails([&](void) {(void) read(spec, text, bad);}, "there is no instance '3' (the file has 2 instances)"));CHECK(fails(spec, text, "the file has 2 instances; select one"));CHECK(equal(read(spec, "3\n4 5 6\n").ints("x"), {4, 5, 6}));Spec s=Spec::parse(spec, "s");Data c=s.catalog_text(text);CHECK(c.integer("instances")==2);CHECK(c.text("name", {1})=="b");Data c1=s.catalog_text("3\n4 5 6\n");CHECK((c1.integer("instances")==1) &&!c1.has("name"));CHECK(Spec::parse("a: int", "s").catalog_text("5").integer("instances")==1);CHECK(fails(spec, "1\n2\njunk\n", "expected a line matching \"{n:int}\""));CHECK(fails("instances { a: int }", "", "the file contains no instance"));CHECK(fails([](void) {(void) Spec::parse("instances { a: int } b: int", "s");}, "'instances' must be the last statement"));CHECK(fails([](void) {(void) Spec::parse("repeat 2 { instances { a: int } }", "s");}, "'instances' must be at the top level"));CHECK(fails("instances { if 0 > 1 { a: int } }", "5", "an instance must read some input"));return true;})