-
Notifications
You must be signed in to change notification settings - Fork 338
/
vrptw.cpp
159 lines (133 loc) · 7.47 KB
/
vrptw.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/*
This file is part of VROOM.
Copyright (c) 2015-2024, Julien Coupey.
All rights reserved (see LICENSE).
*/
#include "problems/vrptw/vrptw.h"
#include "algorithms/heuristics/heuristics.h"
#include "algorithms/local_search/local_search.h"
#include "problems/vrptw/operators/cross_exchange.h"
#include "problems/vrptw/operators/intra_cross_exchange.h"
#include "problems/vrptw/operators/intra_exchange.h"
#include "problems/vrptw/operators/intra_mixed_exchange.h"
#include "problems/vrptw/operators/intra_or_opt.h"
#include "problems/vrptw/operators/intra_relocate.h"
#include "problems/vrptw/operators/intra_two_opt.h"
#include "problems/vrptw/operators/mixed_exchange.h"
#include "problems/vrptw/operators/or_opt.h"
#include "problems/vrptw/operators/pd_shift.h"
#include "problems/vrptw/operators/priority_replace.h"
#include "problems/vrptw/operators/relocate.h"
#include "problems/vrptw/operators/reverse_two_opt.h"
#include "problems/vrptw/operators/route_exchange.h"
#include "problems/vrptw/operators/route_split.h"
#include "problems/vrptw/operators/swap_star.h"
#include "problems/vrptw/operators/tsp_fix.h"
#include "problems/vrptw/operators/two_opt.h"
#include "problems/vrptw/operators/unassigned_exchange.h"
#include "utils/helpers.h"
namespace vroom {
namespace vrptw {
using LocalSearch = ls::LocalSearch<TWRoute,
vrptw::UnassignedExchange,
vrptw::CrossExchange,
vrptw::MixedExchange,
vrptw::TwoOpt,
vrptw::ReverseTwoOpt,
vrptw::Relocate,
vrptw::OrOpt,
vrptw::IntraExchange,
vrptw::IntraCrossExchange,
vrptw::IntraMixedExchange,
vrptw::IntraRelocate,
vrptw::IntraOrOpt,
vrptw::IntraTwoOpt,
vrptw::PDShift,
vrptw::RouteExchange,
vrptw::SwapStar,
vrptw::RouteSplit,
vrptw::PriorityReplace,
vrptw::TSPFix>;
} // namespace vrptw
const std::vector<HeuristicParameters> VRPTW::homogeneous_parameters =
{HeuristicParameters(HEURISTIC::BASIC, INIT::HIGHER_AMOUNT, 0.3),
HeuristicParameters(HEURISTIC::BASIC, INIT::HIGHER_AMOUNT, 0.4),
HeuristicParameters(HEURISTIC::BASIC, INIT::EARLIEST_DEADLINE, 0.2),
HeuristicParameters(HEURISTIC::BASIC, INIT::FURTHEST, 0.3),
HeuristicParameters(HEURISTIC::BASIC, INIT::NONE, 0.4),
HeuristicParameters(HEURISTIC::BASIC, INIT::HIGHER_AMOUNT, 0.5),
HeuristicParameters(HEURISTIC::BASIC, INIT::FURTHEST, 0.4),
HeuristicParameters(HEURISTIC::BASIC, INIT::FURTHEST, 0.5),
HeuristicParameters(HEURISTIC::BASIC, INIT::HIGHER_AMOUNT, 0.1),
HeuristicParameters(HEURISTIC::BASIC, INIT::HIGHER_AMOUNT, 0.6),
HeuristicParameters(HEURISTIC::BASIC, INIT::FURTHEST, 0.2),
HeuristicParameters(HEURISTIC::BASIC, INIT::FURTHEST, 0.7),
HeuristicParameters(HEURISTIC::BASIC, INIT::HIGHER_AMOUNT, 0.2),
HeuristicParameters(HEURISTIC::BASIC, INIT::HIGHER_AMOUNT, 0.7),
HeuristicParameters(HEURISTIC::BASIC, INIT::HIGHER_AMOUNT, 1.4),
HeuristicParameters(HEURISTIC::BASIC, INIT::FURTHEST, 0.1),
HeuristicParameters(HEURISTIC::BASIC, INIT::NONE, 0),
HeuristicParameters(HEURISTIC::BASIC, INIT::NONE, 0.1),
HeuristicParameters(HEURISTIC::BASIC, INIT::NONE, 0.3),
HeuristicParameters(HEURISTIC::BASIC, INIT::NONE, 0.8),
HeuristicParameters(HEURISTIC::BASIC, INIT::EARLIEST_DEADLINE, 0.5),
HeuristicParameters(HEURISTIC::BASIC, INIT::EARLIEST_DEADLINE, 0.8),
HeuristicParameters(HEURISTIC::BASIC, INIT::EARLIEST_DEADLINE, 2.4),
HeuristicParameters(HEURISTIC::BASIC, INIT::FURTHEST, 1.2),
HeuristicParameters(HEURISTIC::BASIC, INIT::NONE, 1),
HeuristicParameters(HEURISTIC::BASIC, INIT::HIGHER_AMOUNT, 1.3),
HeuristicParameters(HEURISTIC::BASIC, INIT::EARLIEST_DEADLINE, 0),
HeuristicParameters(HEURISTIC::BASIC, INIT::EARLIEST_DEADLINE, 0.3),
HeuristicParameters(HEURISTIC::BASIC, INIT::EARLIEST_DEADLINE, 2),
HeuristicParameters(HEURISTIC::BASIC, INIT::FURTHEST, 0),
HeuristicParameters(HEURISTIC::BASIC, INIT::FURTHEST, 0.9),
HeuristicParameters(HEURISTIC::BASIC, INIT::FURTHEST, 1)};
const std::vector<HeuristicParameters> VRPTW::heterogeneous_parameters =
{HeuristicParameters(HEURISTIC::DYNAMIC, INIT::HIGHER_AMOUNT, 0.5),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::HIGHER_AMOUNT, 0.9),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 0.4),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::FURTHEST, 0.4),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::HIGHER_AMOUNT, 0.8),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 0.6),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 0.9),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::FURTHEST, 0.6),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::HIGHER_AMOUNT, 1.8),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 1.1),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 1.4),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::FURTHEST, 0.7),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::NONE, 1.3),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::HIGHER_AMOUNT, 2.4),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 0.3),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::FURTHEST, 1.2),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::NONE, 1.2),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::HIGHER_AMOUNT, 0.6),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::HIGHER_AMOUNT, 1.6),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 0.2),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 1.7),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 2),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::FURTHEST, 0.5),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::FURTHEST, 1.5),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::NONE, 1.5),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::NONE, 2.2),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::HIGHER_AMOUNT, 2.1),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 0.5),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::EARLIEST_DEADLINE, 1.2),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::FURTHEST, 0.1),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::FURTHEST, 0.9),
HeuristicParameters(HEURISTIC::DYNAMIC, INIT::FURTHEST, 1.1)};
VRPTW::VRPTW(const Input& input) : VRP(input) {
}
Solution VRPTW::solve(unsigned nb_searches,
unsigned depth,
unsigned nb_threads,
const Timeout& timeout,
const std::vector<HeuristicParameters>& h_param) const {
return VRP::solve<TWRoute, vrptw::LocalSearch>(nb_searches,
depth,
nb_threads,
timeout,
h_param,
homogeneous_parameters,
heterogeneous_parameters);
}
} // namespace vroom