1626:; (iii) both deterministic and stochastic. We first give in Algorithm 3 the steps of the neighborhood change function which will be used later. Function NeighborhoodChange() compares the new value f(x') with the incumbent value f(x) obtained in the neighborhood k (line 1). If an improvement is obtained, k is returned to its initial value and the new incumbent updated (line 2). Otherwise, the next neighborhood is considered (line 3).
2008:
differ substantially from the incumbent and VNS can then degenerate, to some extent, into the
Multistart heuristic (in which descents are made iteratively from solutions generated at random, a heuristic which is known not to be very efficient). Consequently, some compensation for distance from the incumbent must be made.
2029:
Several ways of parallelizing VNS have recently been proposed for solving the p-Median problem. In García-López et al. three of them are tested: (i) parallelize local search; (ii) augment the number of solutions drawn from the current neighborhood and make a local search in parallel from each
1689:
Function VNS (x, kmax, tmax) 1: repeat 2: k ← 1 3: repeat 4: x' ← Shake(x, k) // Shaking 5: x'' ← BestImprovement(x' ) // Local search 6: x ← NeighbourhoodChange(x, x'', k) // Change neighbourhood 7: until k = kmax 8: t ← CpuTime() 9:
999:
Unlike many other metaheuristics, the basic schemes of VNS and its extensions are simple and require few, and sometimes no parameters. Therefore, in addition to providing very good solutions, often in simpler ways than other methods, VNS gives insight into the reasons for such a performance, which,
2215:
Interest in VNS is growing quickly, evidenced by the increasing number of papers published each year on this topic (10 years ago, only a few; 5 years ago, about a dozen; and about 50 in 2007). Moreover, the 18th EURO mini-conference held in
Tenerife in November 2005 was entirely devoted to VNS. It
2072:
FSS is a method which is very useful because, one problem could be defined in addition formulations and moving through formulations is legitimate. It is proved that local search works within formulations, implying a final solution when started from some initial solution in first formulation. Local
2007:
The skewed VNS (SVNS) method (Hansen et al.) addresses the problem of exploring valleys far from the incumbent solution. Indeed, once the best solution in a large region has been found, it is necessary to go some way to obtain an improved one. Solutions drawn at random in distant neighborhoods may
38:
and global optimization problems. It explores distant neighborhoods of the current incumbent solution, and moves from there to a new one if and only if an improvement was made. The local search method is applied repeatedly to get from solutions in the neighborhood to local optima. VNS was designed
2051:
However, when the dimension of the problem is large, even the relaxed problem may be impossible to solve exactly by standard commercial solvers. Therefore, it seems a good idea to solve dual relaxed problems heuristically as well. It was obtained guaranteed bounds on the primal heuristics
1637:
When VNS does not render a good solution, there are several steps which could be helped in process, such as comparing first and best improvement strategies in local search, reducing neighborhood, intensifying shaking, adopting VND, adopting FSS, and experimenting with parameter settings.
2018:
The variable neighborhood decomposition search (VNDS) method (Hansen et al.) extends the basic VNS into a two-level VNS scheme based upon decomposition of the problem. For ease of presentation, but without loss of generality, it is assumed that the solution x represents the set of some
1033:
in the same direction. If there is no direction of descent, the heuristic stops; otherwise, it is iterated. Usually the highest direction of descent, also related to as best improvement, is used. This set of rules is summarized in
Algorithm 1, where we assume that an initial solution
1680:
is generated at random in Step 4 in order to avoid cycling, which might occur if a deterministic rule were applied. In Step 5, the best improvement local search (Algorithm 1) is usually adopted. However, it can be replaced with first improvement (Algorithm 2).
1718:
th neighborhood. There are two possible variants of this extension: (1) to perform only one local search from the best among b points; (2) to perform all b local searches and then choose the best. In paper (Fleszar and Hindi) could be found algorithm.
1116:
Function FirstImprovement(x) 1: repeat 2: x' ← x; i ← 0 3: repeat 4: i ← i + 1 5: x ← argmin{ f(x), f(x^i)}, x^i ∈ N(x) 6: until ( f(x) < f(x^i) or i = |N(x)| ) 7: until ( f(x) ≥ f(x') ) 8: return x'
1820:
and no descent is made. Rather, the values of these new points are compared with that of the incumbent and an update takes place in case of improvement. It is assumed that a stopping condition has been chosen like the maximum
761:
622:
907:
514:
2062:
The mixed integer linear programming (MILP) problem consists of maximizing or minimizing a linear function, subject to equality or inequality constraints, and integrality restrictions on some of the variables.
1337:
981:
According to (Mladenović, 1995), VNS is a metaheuristic which systematically performs the procedure of neighborhood change, both in descent to local minima and in escape from the valleys which contain them.
374:
2048:
on the objective function value is known. To this end, the standard approach is to relax the integrality condition on the primal variables, based on a mathematical programming formulation of the problem.
1568:
1733:
The variable neighborhood descent (VND) method is obtained if a change of neighborhoods is performed in a deterministic way. In the descriptions of its algorithms, we assume that an initial solution
2044:
For most modern heuristics, the difference in value between the optimal solution and the obtained one is completely unknown. Guaranteed performance of the primal heuristic may be determined if a
1195:
200:
409:, or the solution is unbounded. CPU time has to be finite and short. For continuous optimization, it is reasonable to allow for some degree of tolerance, i.e., to stop when a feasible solution
1634:
Function
NeighborhoodChange (x, x', k) 1: if f (x') < f(x) then 2: x ← x' // Make a move 3: k ← 1 // Initial neighborhood 4: else 5: k ← k+1 // Next neighborhood
1710:
with some probability, even if the solution is worse than the incumbent. It can also be changed into a first improvement method. Another variant of the basic VNS can be to find a solution
2595:
Mladenović, N.; Petrovic, J.; Kovacevic-Vujcic, V.; Cangalovic, M. (2003b). "Solving spread spectrum radar polyphase code design problem by tabu search and variable neighborhood search".
1422:
626:
Some heuristics speedily accept an approximate solution, or optimal solution but one with no validation of its optimality. Some of them have an incorrect certificate, i.e., the solution
1818:
1511:
1377:
1235:
1674:
1617:
407:
1098:
300:
781:
262:
945:
1991:
1958:
1925:
1892:
1856:
1768:
1463:
972:
811:
651:
434:
2030:
of them and (iii) do the same as (ii) but update the information about the best solution found. Three
Parallel VNS strategies are also suggested for solving the
2217:
2052:
performance. In Primal-dual VNS (PD-VNS) (Hansen et al.) one possible general way to attain both the guaranteed bounds and the exact solution is proposed.
1737:
is given. Most local search heuristics in their descent phase use very few neighborhoods. The final solution should be a local minimum with respect to all
1003:
There are several papers where it could be studied among recently mentioned, such as (Hansen and
Mladenović 1999, 2001a, 2003, 2005; Moreno-Pérez et al.;)
1702:
with randomization. Without much additional effort, it can be transformed into a descent-ascent method: in
NeighbourhoodChange() function, replace also
658:
519:
383:, with the validation of its optimal structure, or if it is unrealizable, in procedure have to be shown that there is no achievable solution, i.e.,
35:
2102:
Applications of VNS, or of varieties of VNS are very abundant and numerous. Some fields where it could be found collections of scientific papers:
818:
1993:
is often 2. In addition, the maximum number of iterations between two improvements is usually used as a stopping condition. RVNS is akin to a
2856:
2361:
441:
2905:
1645:, 2010) combines deterministic and stochastic changes of neighborhood. Its steps are given in Algorithm 4. Often successive neighborhoods
1108:
Function BestImprovement(x) 1: repeat 2: x' ← x 3: x ← argmin_{ f(y) }, y ∈ N(x) 4: until ( f(x) ≥ f(x') ) 5: return x'
1100:
are then enumerated systematically and a move is made as soon as a direction for the descent is found. This is summarized in
Algorithm 2.
1960:. RVNS is useful in very large instances, for which local search is costly. It has been observed that the best value for the parameter
2521:
2676:
García-López, F; Melián-Batista, B; Moreno-Pérez, JA (2002). "The parallel variable neighborhood search for the p-median problem".
307:
105:, 2010, Handbook of Metaheuristics, 2003 and Search methodologies, 2005. Earlier work that motivated this approach can be found in
2440:
Brimberg, J.; Mladenović, N. (1996). "A variable neighborhood algorithm for solving the continuous location-allocation problem".
1622:
In order to solve problem by using several neighborhoods, facts 1–3 can be used in three different ways: (i) deterministic; (ii)
989:
A local minimum with respect to one neighborhood structure is not necessarily a local minimum for another neighborhood structure.
2537:
Fleszar, K; Hindi, KS (2004). "Solving the resource-constrained project scheduling problem by a variable neighbourhood search".
1251:
39:
for approximating solutions of discrete and continuous optimization problems and according to these, it is aimed for solving
1516:
2833:. International Series in Operations Research & Management Science. Vol. 57. Dordrecht: Kluwer. pp. 145–184.
1770:
neighborhoods; hence the chances to reach a global one are larger when using VND than with a single neighborhood structure.
1123:
139:
2031:
786:
Heuristics are faced with the problem of local optima as a result of avoiding boundless computing time. A local optimum
2086:
1017:
A local search heuristic is performed through choosing an initial solution x, discovering a direction of descent from
1012:
122:
Recent surveys on VNS methodology as well as numerous applications can be found in 4OR, 2008 and Annals of OR, 2010.
83:
1058:
is explored completely. As this may be time-consuming, an alternative is to use the first descent heuristic. Vectors
2900:
2074:
1699:
2626:; Mladenović, N; Parreira, A (2000). "Variable neighborhood search for weighted maximum satisfiability problem".
2494:
Moreno-Pérez, JA.; Hansen, P.; Mladenović, N. (2005). "Parallel variable neighborhood search". In Alba, E (ed.).
222:
995:
For many problems, local minima with respect to one or several neighborhoods are relatively close to each other.
2425:
Mladenović, N. (1995). "A variable neighborhood algorithm—a new metaheuristic for combinatorial optimization".
2245:
Hansen, P.; Mladenović, N.; Perez, J.A.M. (2010). "Variable neighbourhood search: methods and applications".
2221:
2459:
Hansen, P.; Mladenović, N.; Perez, J.A.M (2008). "Variable neighbourhood search: methods and applications".
2142:
2090:
1382:
87:
79:
1783:
1476:
1342:
1200:
2834:
2770:
2499:
2289:
2190:
Effectiveness: VNS supplies optimal or near-optimal solutions for all or at least most realistic instances
2045:
2082:
1648:
48:
2177:
VNS implies several features which are presented by Hansen and
Mladenović and some are presented here:
2829:
Hansen, P; Mladenović, N (2003). "Variable neighborhood search". In Glover F; Kochenberger G (eds.).
2761:
Hansen, P.; Mladenović, N.; Urosevic, D. (2006). "Variable neighborhood search and local branching".
2211:
Multiplicity: VNS is able to produce a certain near-optimal solutions from which the user can choose;
1425:
131:
2839:
2504:
2294:
386:
2775:
2225:
1573:
1061:
270:
2693:
2658:
2476:
2262:
2208:
Interactivity: VNS allows the user to incorporate his knowledge to improve the resolution process
1994:
44:
40:
2333:
Glover, F.; Kochenberger, G.A. (2003). "Handbook of
Metaheuristics". Kluwer Academic Publishers.
2641:
Hansen, P; Mladenović, N; Pérez-Brito, D (2001). "Variable neighborhood decomposition search".
2199:
User friendliness: VNS has no parameters, so it is easy for understanding, expressing and using
766:
232:
2852:
2517:
2357:
1714:
in the 'Shaking' step as the best among b (a parameter) randomly generated solutions from the
1466:
914:
2193:
Efficiency: VNS takes a moderate computing time to generate optimal or near-optimal solutions
1963:
1930:
1897:
1864:
1828:
1740:
1435:
2844:
2811:
2780:
2743:
2685:
2650:
2623:
2604:
2577:
2546:
2509:
2468:
2405:
2349:
2346:
Search methodologies. Introductory tutorials in optimization and decision support techniques
2299:
2254:
2187:
Coherence: all actions of the heuristics for solving problems follow from the VNS principles
2125:
2078:
71:
17:
2073:
search systematically alternates between different formulations which was investigated for
950:
789:
629:
412:
67:
992:
A global minimum is a local minimum with respect to all possible neighborhood structures.
2799:
2875:
2608:
2550:
2303:
59:
VNS systematically changes the neighborhood in two phases: firstly, descent to find a
2894:
2712:
2566:"Improvements and comparison of heuristics for solving the multisource Weber problem"
91:
60:
31:
2697:
2662:
2266:
2802:; Urosevic, D. (2006). "Reformulation descent applied to circle packing problems".
2120:
2480:
756:{\displaystyle {(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}}
95:
617:{\displaystyle {(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}}
221:
are the solution space, the feasible set, a feasible solution, and a real-valued
2732:"Primal-dual variable neighborhood search for the simple plant location problem"
2581:
2147:
2115:
2713:"Metaheuristics based on GRASP and VNS for solving traveling purchaser problem"
229:
is a finite but large set, a combinatorial optimization problem is defined. If
2815:
2784:
2689:
2654:
2472:
2353:
2258:
2196:
Robustness: the functioning of the VNS is coherent over a variety of instances
2137:
1623:
75:
2410:
2393:
1780:
The reduced VNS (RVNS) method is obtained if random points are selected from
2848:
2731:
2565:
2513:
2747:
2322:
Gendreau, M.; Potvin, J-Y. (2010). "Handbook of Metaheuristics". Springer.
2222:
http://www.journals.elsevier.com/european-journal-of-operational-research/
2205:
Generality: VNS is inducing to good results for a wide variety of problems
902:{\displaystyle {f(x_{L})\leq f(x),\qquad \forall {x}\,\in N(x_{L})\cap X}}
66:
Applications are rapidly increasing in number and pertain to many fields:
63:
and finally, a perturbation phase to get out of the corresponding valley.
2344:
Burke, EK.; Kendall, G. (2005). Burke, Edmund K; Kendall, Graham (eds.).
1822:
2280:
Nenad Mladenović; Pierre Hansen (1997). "Variable neighborhood search".
1469:) is a feasible solution where a minimum of problem is reached. We call
1000:
in turn, can lead to more efficient and sophisticated implementations.
509:{\displaystyle {f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}}
2377:
Davidon, W.C. (1959). "Variable metric algorithm for minimization".
379:
Exact algorithm for problem (1) is to be found an optimal solution
101:
There are several books important for understanding VNS, such as:
1197:, a finite set of pre-selected neighborhood structures, and with
2886:
The 8th International Conference on Variable Neighborhood Search
2881:
The 5th International Conference on Variable Neighborhood Search
2880:
2226:
https://www.springer.com/mathematics/applications/journal/10732/
2184:
Precision: VNS is formulated in precise mathematical definitions
2564:
Brimberg, J.; Hansen, P.; Mladenović, N.; Taillard, E. (2000).
2885:
2730:
Hansen, P; Brimberg, J; Uroševi´c, D; Mladenović, N (2007a).
1858:
or the maximum number of iterations between two improvements.
1428:(or quasi-metric) functions introduced into a solution space
1038:
is given. The output consists of a local minimum, denoted by
369:{\displaystyle {f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}}
2876:
EURO Mini Conference XXVIII on Variable Neighbourhood Search
2427:
Abstracts of Papers Presented at Optimization Days, Montréal
1790:
1655:
1530:
1483:
1390:
1349:
1259:
1207:
1130:
2181:
Simplicity: VNS is simple, clear and universally applicable
1861:
To simplify the description of the algorithms it is used
1104:
Algorithm 1: Best improvement (highest descent) heuristic
30:(VNS), proposed by Mladenović & Hansen in 1997, is a
1112:
Algorithm 2: First improvement (first descent) heuristic
1332:{\displaystyle {\mathcal {N'}}_{k}(x),k=1,...,k'_{max}}
1042:, and its value. Observe that a neighborhood structure
2202:
Innovation: VNS is generating new types of application
1563:{\displaystyle x\in {\mathcal {N'}}_{k}(x)\subseteq X}
1966:
1933:
1900:
1867:
1831:
1786:
1743:
1651:
1576:
1519:
1479:
1438:
1385:
1345:
1254:
1203:
1126:
1064:
953:
917:
821:
792:
769:
661:
632:
522:
444:
415:
389:
310:
273:
235:
142:
2628:
Les Cahiers du GERAD G–2000–62, HEC Montréal, Canada
2394:"Rapidly convergent descent method for minimization"
2220:
in 2007, European Journal of Operational Research (
1190:{\displaystyle {\mathcal {N}}_{k}(k=1,...,k_{max})}
195:{\displaystyle \min {\{f(x)|x\in X,X\subseteq S\}}}
2496:Parallel Metaheuristics: A New Class of Algorithms
1985:
1952:
1919:
1886:
1850:
1812:
1762:
1668:
1611:
1562:
1505:
1457:
1416:
1371:
1331:
1229:
1189:
1092:
966:
939:
901:
805:
775:
755:
645:
616:
508:
428:
401:
368:
294:
256:
194:
143:
2067:Variable Neighborhood Formulation Space Search
1339:when describing local descent. Neighborhoods
985:VNS is built upon the following perceptions:
8:
1894:below. Therefore, RVNS uses two parameters:
188:
147:
2379:Argonne National Laboratory Report ANL-5990
1473:a local minimum of problem with respect to
98:, geometry, telecommunication design, etc.
2013:Variable Neighborhood Decomposition Search
264:, there is continuous optimization model.
90:, engineering, pooling problems, biology,
47:problems, mixed integer program problems,
2838:
2774:
2711:Ochi, LS; Silva, MB; Drummond, L (2001).
2503:
2409:
2317:
2315:
2313:
2293:
1971:
1965:
1938:
1932:
1905:
1899:
1872:
1866:
1836:
1830:
1795:
1789:
1788:
1785:
1748:
1742:
1660:
1654:
1653:
1650:
1575:
1539:
1528:
1527:
1518:
1488:
1482:
1481:
1478:
1443:
1437:
1399:
1388:
1387:
1384:
1354:
1348:
1347:
1344:
1314:
1268:
1257:
1256:
1253:
1212:
1206:
1205:
1202:
1172:
1135:
1129:
1128:
1125:
1069:
1063:
958:
952:
928:
916:
883:
869:
864:
833:
822:
820:
797:
791:
768:
745:
740:
718:
703:
676:
662:
660:
637:
631:
606:
601:
579:
564:
537:
523:
521:
498:
493:
456:
445:
443:
420:
414:
388:
358:
353:
322:
311:
309:
279:
274:
272:
247:
236:
234:
162:
146:
141:
2237:
1630:Algorithm 3: – Neighborhood change
396:
2089:is not strictly a stationary point in
1417:{\displaystyle {\mathcal {N'}}_{k}(x)}
2392:Fletcher, R.; Powell, M.J.D. (1963).
2218:IMA Journal of Management Mathematics
2159:Problems in biosciences and chemistry
1813:{\displaystyle {\mathcal {N}}_{k}(x)}
1506:{\displaystyle {\mathcal {N}}_{k}(x)}
1372:{\displaystyle {\mathcal {N}}_{k}(x)}
1230:{\displaystyle {\mathcal {N}}_{k}(x)}
7:
1698:The basic VNS is a best improvement
1676:will be nested. Observe that point
1025:, and proceeding to the minimum of
1669:{\displaystyle {\mathcal {N}}_{k}}
861:
737:
598:
490:
350:
25:
2804:Computers and Operations Research
2763:Computers and Operations Research
2282:Computers and Operations Research
2156:Extended vehicle routing problems
1050:. At each step, the neighborhood
2109:Design problems in communication
1424:may be induced from one or more
2057:Variable Neighborhood Branching
1248:One will also use the notation
860:
783:, though this is rarely small.
736:
597:
489:
349:
2224:), and Journal of Heuristics (
1807:
1801:
1606:
1595:
1586:
1580:
1551:
1545:
1500:
1494:
1411:
1405:
1366:
1360:
1280:
1274:
1224:
1218:
1184:
1141:
1087:
1081:
934:
921:
889:
876:
854:
848:
839:
826:
724:
711:
700:
697:
691:
682:
669:
663:
585:
572:
561:
558:
552:
543:
530:
524:
477:
471:
462:
449:
402:{\displaystyle X=\varnothing }
343:
337:
328:
315:
163:
159:
153:
1:
2609:10.1016/s0377-2217(02)00833-0
2551:10.1016/s0377-2217(02)00884-6
2304:10.1016/s0305-0548(97)00031-2
2247:Annals of Operations Research
1641:The Basic VNS (BVNS) method (
1612:{\displaystyle f(x)<f(x')}
1093:{\displaystyle x^{i}\in N(x)}
2032:Travelling purchaser problem
1237:the set of solutions in the
295:{\displaystyle {x^{*}\in X}}
118:Brimberg, J., Mladenović, N.
112:Fletcher, R., Powell, M.J.D.
34:method for solving a set of
28:Variable neighborhood search
18:Variable Neighborhood Search
2906:Travelling salesman problem
2582:10.1287/opre.48.3.444.12431
2165:Other optimization problems
1013:Local search (optimization)
2922:
2831:Handbook of Metaheuristics
1643:Handbook of Metaheuristics
1513:, if there is no solution
1010:
947:denotes a neighborhood of
103:Handbook of Metaheuristics
36:combinatorial optimization
2816:10.1016/j.cor.2004.03.010
2785:10.1016/j.cor.2005.02.033
2473:10.1007/s10288-008-0089-1
2354:10.1007/978-1-4614-6940-7
2259:10.1007/s10479-009-0657-6
2216:led to special issues of
1997:, but is more systematic.
776:{\displaystyle \epsilon }
436:has been found such that
257:{\displaystyle {S=R^{n}}}
130:Define one deterministic
126:Definition of the problem
2143:Vehicle routing problems
1021:, within a neighborhood
940:{\displaystyle N(x_{L})}
813:of problem is such that
2849:10.1007/0-306-48056-5_6
2690:10.1023/A:1015013919497
2655:10.1023/A:1011336210885
2514:10.1002/0471739383.ch11
2162:Continuous optimization
2106:Industrial applications
1986:{\displaystyle k_{max}}
1953:{\displaystyle k_{max}}
1920:{\displaystyle t_{max}}
1887:{\displaystyle t_{max}}
1851:{\displaystyle t_{max}}
1763:{\displaystyle k_{max}}
1458:{\displaystyle x_{opt}}
88:artificial intelligence
2748:10.1287/ijoc.1060.0196
2411:10.1093/comjnl/6.2.163
2131:Mixed integer problems
2085:formulation of CPP in
1987:
1954:
1921:
1888:
1852:
1814:
1764:
1685:Algorithm 4: Basic VNS
1670:
1613:
1564:
1507:
1459:
1432:. An optimal solution
1418:
1373:
1333:
1231:
1191:
1094:
968:
941:
903:
807:
777:
757:
647:
618:
510:
430:
403:
370:
296:
258:
196:
2087:Cartesian coordinates
2083:nonlinear programming
1988:
1955:
1922:
1889:
1853:
1815:
1765:
1671:
1614:
1565:
1508:
1460:
1419:
1374:
1334:
1232:
1192:
1095:
969:
967:{\displaystyle x_{L}}
942:
904:
808:
806:{\displaystyle x_{L}}
778:
758:
648:
646:{\displaystyle x_{h}}
619:
511:
431:
429:{\displaystyle x^{*}}
404:
371:
297:
259:
197:
2498:. pp. 247–266.
2153:Fleet sheet problems
2150:and waste collection
2128:and packing problems
2077:problem (CPP) where
1964:
1931:
1898:
1865:
1829:
1784:
1741:
1649:
1574:
1517:
1477:
1436:
1383:
1343:
1252:
1201:
1124:
1062:
951:
915:
819:
790:
767:
659:
630:
520:
442:
413:
387:
308:
271:
233:
140:
132:optimization problem
1328:
1046:is defined for all
653:obtained satisfies
225:, respectively. If
1995:Monte-Carlo method
1983:
1950:
1917:
1884:
1848:
1810:
1760:
1690:until t > tmax
1666:
1609:
1560:
1503:
1455:
1414:
1369:
1329:
1310:
1227:
1187:
1090:
964:
937:
899:
803:
773:
753:
643:
614:
506:
426:
399:
366:
292:
254:
223:objective function
192:
115:Mladenović, N. and
2901:Search algorithms
2858:978-1-4020-7263-5
2769:(10): 3034–3045.
2597:Eur. J. Oper. Res
2442:Stud. Locat. Anal
2363:978-1-4614-6939-1
2288:(11): 1097–1100.
2168:Discovery science
2112:Location problems
2091:polar coordinates
49:nonlinear program
16:(Redirected from
2913:
2863:
2862:
2842:
2826:
2820:
2819:
2810:(9): 2419–2434.
2798:Mladenović, N.;
2795:
2789:
2788:
2778:
2758:
2752:
2751:
2736:INFORMS J Comput
2727:
2721:
2720:
2708:
2702:
2701:
2673:
2667:
2666:
2638:
2632:
2631:
2619:
2613:
2612:
2592:
2586:
2585:
2561:
2555:
2554:
2534:
2528:
2527:
2507:
2491:
2485:
2484:
2456:
2450:
2449:
2437:
2431:
2430:
2422:
2416:
2415:
2413:
2389:
2383:
2382:
2374:
2368:
2367:
2341:
2335:
2334:
2330:
2324:
2323:
2319:
2308:
2307:
2297:
2277:
2271:
2270:
2242:
2079:stationary point
1992:
1990:
1989:
1984:
1982:
1981:
1959:
1957:
1956:
1951:
1949:
1948:
1926:
1924:
1923:
1918:
1916:
1915:
1893:
1891:
1890:
1885:
1883:
1882:
1857:
1855:
1854:
1849:
1847:
1846:
1819:
1817:
1816:
1811:
1800:
1799:
1794:
1793:
1769:
1767:
1766:
1761:
1759:
1758:
1675:
1673:
1672:
1667:
1665:
1664:
1659:
1658:
1618:
1616:
1615:
1610:
1605:
1569:
1567:
1566:
1561:
1544:
1543:
1538:
1537:
1536:
1512:
1510:
1509:
1504:
1493:
1492:
1487:
1486:
1464:
1462:
1461:
1456:
1454:
1453:
1423:
1421:
1420:
1415:
1404:
1403:
1398:
1397:
1396:
1378:
1376:
1375:
1370:
1359:
1358:
1353:
1352:
1338:
1336:
1335:
1330:
1324:
1273:
1272:
1267:
1266:
1265:
1241:neighborhood of
1236:
1234:
1233:
1228:
1217:
1216:
1211:
1210:
1196:
1194:
1193:
1188:
1183:
1182:
1140:
1139:
1134:
1133:
1099:
1097:
1096:
1091:
1074:
1073:
973:
971:
970:
965:
963:
962:
946:
944:
943:
938:
933:
932:
908:
906:
905:
900:
898:
888:
887:
868:
838:
837:
812:
810:
809:
804:
802:
801:
782:
780:
779:
774:
762:
760:
759:
754:
752:
744:
723:
722:
707:
681:
680:
652:
650:
649:
644:
642:
641:
623:
621:
620:
615:
613:
605:
584:
583:
568:
542:
541:
515:
513:
512:
507:
505:
497:
461:
460:
435:
433:
432:
427:
425:
424:
408:
406:
405:
400:
375:
373:
372:
367:
365:
357:
327:
326:
301:
299:
298:
293:
291:
284:
283:
263:
261:
260:
255:
253:
252:
251:
201:
199:
198:
193:
191:
166:
72:cluster analysis
21:
2921:
2920:
2916:
2915:
2914:
2912:
2911:
2910:
2891:
2890:
2872:
2867:
2866:
2859:
2840:10.1.1.635.7056
2828:
2827:
2823:
2797:
2796:
2792:
2760:
2759:
2755:
2729:
2728:
2724:
2717:MIC'2001, Porto
2710:
2709:
2705:
2675:
2674:
2670:
2640:
2639:
2635:
2621:
2620:
2616:
2594:
2593:
2589:
2563:
2562:
2558:
2536:
2535:
2531:
2524:
2505:10.1.1.615.2796
2493:
2492:
2488:
2458:
2457:
2453:
2439:
2438:
2434:
2424:
2423:
2419:
2391:
2390:
2386:
2376:
2375:
2371:
2364:
2343:
2342:
2338:
2332:
2331:
2327:
2321:
2320:
2311:
2295:10.1.1.800.1797
2279:
2278:
2274:
2244:
2243:
2239:
2234:
2175:
2100:
2039:Primal-dual VNS
1967:
1962:
1961:
1934:
1929:
1928:
1901:
1896:
1895:
1868:
1863:
1862:
1832:
1827:
1826:
1787:
1782:
1781:
1744:
1739:
1738:
1725:
1696:
1691:
1687:
1652:
1647:
1646:
1635:
1632:
1598:
1572:
1571:
1529:
1526:
1515:
1514:
1480:
1475:
1474:
1439:
1434:
1433:
1389:
1386:
1381:
1380:
1346:
1341:
1340:
1258:
1255:
1250:
1249:
1204:
1199:
1198:
1168:
1127:
1122:
1121:
1120:Let one denote
1118:
1114:
1109:
1106:
1065:
1060:
1059:
1015:
1009:
979:
954:
949:
948:
924:
913:
912:
879:
829:
817:
816:
793:
788:
787:
765:
764:
714:
672:
657:
656:
633:
628:
627:
575:
533:
518:
517:
452:
440:
439:
416:
411:
410:
385:
384:
318:
306:
305:
275:
269:
268:
243:
231:
230:
138:
137:
128:
80:vehicle routing
68:location theory
57:
51:problems, etc.
45:integer program
23:
22:
15:
12:
11:
5:
2919:
2917:
2909:
2908:
2903:
2893:
2892:
2889:
2888:
2883:
2878:
2871:
2870:External links
2868:
2865:
2864:
2857:
2821:
2790:
2776:10.1.1.108.987
2753:
2742:(4): 552–564.
2722:
2703:
2684:(3): 375–388.
2668:
2649:(4): 335–350.
2633:
2614:
2603:(2): 389–399.
2587:
2576:(3): 444–460.
2556:
2545:(2): 402–413.
2539:Eur J Oper Res
2529:
2522:
2486:
2467:(4): 319–360.
2451:
2432:
2417:
2404:(2): 163–168.
2384:
2369:
2362:
2336:
2325:
2309:
2272:
2236:
2235:
2233:
2230:
2213:
2212:
2209:
2206:
2203:
2200:
2197:
2194:
2191:
2188:
2185:
2182:
2174:
2171:
2170:
2169:
2166:
2163:
2160:
2157:
2154:
2151:
2145:
2140:
2135:
2132:
2129:
2123:
2121:Graph problems
2118:
2113:
2110:
2107:
2099:
2096:
2095:
2094:
2075:circle packing
2069:
2068:
2064:
2063:
2059:
2058:
2054:
2053:
2049:
2041:
2040:
2036:
2035:
2034:in Ochi et al.
2026:
2025:
2021:
2020:
2015:
2014:
2010:
2009:
2004:
2003:
1999:
1998:
1980:
1977:
1974:
1970:
1947:
1944:
1941:
1937:
1914:
1911:
1908:
1904:
1881:
1878:
1875:
1871:
1859:
1845:
1842:
1839:
1835:
1809:
1806:
1803:
1798:
1792:
1777:
1776:
1772:
1771:
1757:
1754:
1751:
1747:
1730:
1729:
1724:
1721:
1700:descent method
1695:
1692:
1688:
1686:
1683:
1663:
1657:
1633:
1631:
1628:
1608:
1604:
1601:
1597:
1594:
1591:
1588:
1585:
1582:
1579:
1559:
1556:
1553:
1550:
1547:
1542:
1535:
1532:
1525:
1522:
1502:
1499:
1496:
1491:
1485:
1467:global minimum
1452:
1449:
1446:
1442:
1413:
1410:
1407:
1402:
1395:
1392:
1368:
1365:
1362:
1357:
1351:
1327:
1323:
1320:
1317:
1313:
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1271:
1264:
1261:
1226:
1223:
1220:
1215:
1209:
1186:
1181:
1178:
1175:
1171:
1167:
1164:
1161:
1158:
1155:
1152:
1149:
1146:
1143:
1138:
1132:
1115:
1113:
1110:
1107:
1105:
1102:
1089:
1086:
1083:
1080:
1077:
1072:
1068:
1008:
1005:
997:
996:
993:
990:
978:
975:
961:
957:
936:
931:
927:
923:
920:
897:
894:
891:
886:
882:
878:
875:
872:
867:
863:
859:
856:
853:
850:
847:
844:
841:
836:
832:
828:
825:
800:
796:
772:
751:
748:
743:
739:
735:
732:
729:
726:
721:
717:
713:
710:
706:
702:
699:
696:
693:
690:
687:
684:
679:
675:
671:
668:
665:
640:
636:
612:
609:
604:
600:
596:
593:
590:
587:
582:
578:
574:
571:
567:
563:
560:
557:
554:
551:
548:
545:
540:
536:
532:
529:
526:
504:
501:
496:
492:
488:
485:
482:
479:
476:
473:
470:
467:
464:
459:
455:
451:
448:
423:
419:
398:
395:
392:
364:
361:
356:
352:
348:
345:
342:
339:
336:
333:
330:
325:
321:
317:
314:
302:is optimal if
290:
287:
282:
278:
250:
246:
242:
239:
190:
187:
184:
181:
178:
175:
172:
169:
165:
161:
158:
155:
152:
149:
145:
127:
124:
120:
119:
116:
113:
110:
86:, lot-sizing,
84:network design
56:
53:
41:linear program
24:
14:
13:
10:
9:
6:
4:
3:
2:
2918:
2907:
2904:
2902:
2899:
2898:
2896:
2887:
2884:
2882:
2879:
2877:
2874:
2873:
2869:
2860:
2854:
2850:
2846:
2841:
2836:
2832:
2825:
2822:
2817:
2813:
2809:
2805:
2801:
2794:
2791:
2786:
2782:
2777:
2772:
2768:
2764:
2757:
2754:
2749:
2745:
2741:
2737:
2733:
2726:
2723:
2718:
2714:
2707:
2704:
2699:
2695:
2691:
2687:
2683:
2679:
2672:
2669:
2664:
2660:
2656:
2652:
2648:
2644:
2637:
2634:
2629:
2625:
2618:
2615:
2610:
2606:
2602:
2598:
2591:
2588:
2583:
2579:
2575:
2571:
2567:
2560:
2557:
2552:
2548:
2544:
2540:
2533:
2530:
2525:
2523:9780471739388
2519:
2515:
2511:
2506:
2501:
2497:
2490:
2487:
2482:
2478:
2474:
2470:
2466:
2462:
2455:
2452:
2447:
2443:
2436:
2433:
2428:
2421:
2418:
2412:
2407:
2403:
2399:
2395:
2388:
2385:
2380:
2373:
2370:
2365:
2359:
2355:
2351:
2347:
2340:
2337:
2329:
2326:
2318:
2316:
2314:
2310:
2305:
2301:
2296:
2291:
2287:
2283:
2276:
2273:
2268:
2264:
2260:
2256:
2252:
2248:
2241:
2238:
2231:
2229:
2227:
2223:
2219:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2186:
2183:
2180:
2179:
2178:
2172:
2167:
2164:
2161:
2158:
2155:
2152:
2149:
2146:
2144:
2141:
2139:
2136:
2133:
2130:
2127:
2124:
2122:
2119:
2117:
2114:
2111:
2108:
2105:
2104:
2103:
2097:
2092:
2088:
2084:
2080:
2076:
2071:
2070:
2066:
2065:
2061:
2060:
2056:
2055:
2050:
2047:
2043:
2042:
2038:
2037:
2033:
2028:
2027:
2023:
2022:
2017:
2016:
2012:
2011:
2006:
2005:
2001:
2000:
1996:
1978:
1975:
1972:
1968:
1945:
1942:
1939:
1935:
1912:
1909:
1906:
1902:
1879:
1876:
1873:
1869:
1860:
1843:
1840:
1837:
1833:
1824:
1804:
1796:
1779:
1778:
1774:
1773:
1755:
1752:
1749:
1745:
1736:
1732:
1731:
1727:
1726:
1722:
1720:
1717:
1713:
1709:
1705:
1701:
1693:
1684:
1682:
1679:
1661:
1644:
1639:
1629:
1627:
1625:
1620:
1602:
1599:
1592:
1589:
1583:
1577:
1557:
1554:
1548:
1540:
1533:
1523:
1520:
1497:
1489:
1472:
1468:
1450:
1447:
1444:
1440:
1431:
1427:
1408:
1400:
1393:
1363:
1355:
1325:
1321:
1318:
1315:
1311:
1307:
1304:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1277:
1269:
1262:
1246:
1244:
1240:
1221:
1213:
1179:
1176:
1173:
1169:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1136:
1111:
1103:
1101:
1084:
1078:
1075:
1070:
1066:
1057:
1053:
1049:
1045:
1041:
1037:
1032:
1028:
1024:
1020:
1014:
1006:
1004:
1001:
994:
991:
988:
987:
986:
983:
976:
974:
959:
955:
929:
925:
918:
909:
895:
892:
884:
880:
873:
870:
865:
857:
851:
845:
842:
834:
830:
823:
814:
798:
794:
784:
770:
749:
746:
741:
733:
730:
727:
719:
715:
708:
704:
694:
688:
685:
677:
673:
666:
654:
638:
634:
624:
610:
607:
602:
594:
591:
588:
580:
576:
569:
565:
555:
549:
546:
538:
534:
527:
502:
499:
494:
486:
483:
480:
474:
468:
465:
457:
453:
446:
437:
421:
417:
393:
390:
382:
377:
362:
359:
354:
346:
340:
334:
331:
323:
319:
312:
303:
288:
285:
280:
276:
265:
248:
244:
240:
237:
228:
224:
220:
216:
212:
208:
203:
185:
182:
179:
176:
173:
170:
167:
156:
150:
135:
133:
125:
123:
117:
114:
111:
109:Davidon, W.C.
108:
107:
106:
104:
99:
97:
93:
89:
85:
81:
77:
73:
69:
64:
62:
61:local optimum
54:
52:
50:
46:
42:
37:
33:
32:metaheuristic
29:
19:
2830:
2824:
2807:
2803:
2800:Plastria, F.
2793:
2766:
2762:
2756:
2739:
2735:
2725:
2716:
2706:
2681:
2678:J Heuristics
2677:
2671:
2646:
2643:J Heuristics
2642:
2636:
2627:
2622:Hansen, P.;
2617:
2600:
2596:
2590:
2573:
2569:
2559:
2542:
2538:
2532:
2495:
2489:
2464:
2460:
2454:
2445:
2441:
2435:
2426:
2420:
2401:
2397:
2387:
2378:
2372:
2348:. Springer.
2345:
2339:
2328:
2285:
2281:
2275:
2250:
2246:
2240:
2214:
2176:
2134:Time tabling
2101:
2098:Applications
2024:Parallel VNS
1734:
1715:
1711:
1707:
1703:
1697:
1694:VNS variants
1677:
1642:
1640:
1636:
1621:
1470:
1429:
1247:
1242:
1238:
1119:
1055:
1051:
1047:
1043:
1039:
1035:
1030:
1026:
1022:
1018:
1016:
1007:Local search
1002:
998:
984:
980:
910:
815:
785:
655:
625:
438:
380:
378:
304:
266:
226:
218:
214:
210:
206:
204:
136:
129:
121:
102:
100:
65:
58:
55:Introduction
27:
26:
2253:: 367–407.
2228:) in 2008.
2148:Arc routing
2116:Data mining
2046:lower bound
977:Description
267:A solution
96:reliability
2895:Categories
2719:: 489–494.
2624:Jaumard, B
2232:References
2173:Conclusion
2138:Scheduling
2002:Skewed VNS
1723:Extensions
1624:stochastic
1570:such that
1011:See also:
76:scheduling
43:problems,
2835:CiteSeerX
2771:CiteSeerX
2570:Oper. Res
2500:CiteSeerX
2398:Comput. J
2290:CiteSeerX
2019:elements.
1555:⊆
1524:∈
1076:∈
893:∩
871:∈
862:∀
843:≤
771:ϵ
763:for some
747:∈
738:∀
731:ϵ
728:≤
686:−
608:∈
599:∀
592:ϵ
581:∗
547:−
539:∗
500:∈
491:∀
484:ϵ
466:≤
458:∗
422:∗
397:∅
360:∈
351:∀
332:≤
324:∗
286:∈
281:∗
183:⊆
171:∈
92:phylogeny
2698:16096161
2663:31111583
2267:26469746
2126:Knapsack
1825:allowed
1823:CPU time
1603:′
1534:′
1394:′
1326:′
1263:′
2448:: 1–12.
1029:within
2855:
2837:
2773:
2696:
2661:
2520:
2502:
2481:538959
2479:
2429:: 112.
2360:
2292:
2265:
2081:for a
1471:x' ∈ X
1426:metric
911:where
217:, and
205:where
202:, (1)
2694:S2CID
2659:S2CID
2477:S2CID
2263:S2CID
1048:x ∈ X
134:with
2853:ISBN
2518:ISBN
2358:ISBN
1927:and
1775:RVNS
1590:<
1465:(or
1052:N(x)
1044:N(x)
1031:N(x)
1027:f(x)
1023:N(x)
589:<
2845:doi
2812:doi
2781:doi
2744:doi
2686:doi
2651:doi
2605:doi
2601:151
2578:doi
2547:doi
2543:155
2510:doi
2469:doi
2461:4OR
2406:doi
2350:doi
2300:doi
2255:doi
2251:175
1728:VND
1706:by
1379:or
1239:kth
1054:of
516:or
144:min
2897::
2851:.
2843:.
2808:32
2806:.
2779:.
2767:33
2765:.
2740:19
2738:.
2734:.
2715:.
2692:.
2680:.
2657:.
2645:.
2599:.
2574:48
2572:.
2568:.
2541:.
2516:.
2508:.
2475:.
2463:.
2446:10
2444:.
2400:.
2396:.
2356:.
2312:^
2298:.
2286:24
2284:.
2261:.
2249:.
1712:x'
1708:x"
1678:x'
1619:.
1245:.
1040:x'
381:x*
376:.
213:,
209:,
94:,
82:,
78:,
74:,
70:,
2861:.
2847::
2818:.
2814::
2787:.
2783::
2750:.
2746::
2700:.
2688::
2682:8
2665:.
2653::
2647:7
2630:.
2611:.
2607::
2584:.
2580::
2553:.
2549::
2526:.
2512::
2483:.
2471::
2465:6
2414:.
2408::
2402:6
2381:.
2366:.
2352::
2306:.
2302::
2269:.
2257::
2093:.
1979:x
1976:a
1973:m
1969:k
1946:x
1943:a
1940:m
1936:k
1913:x
1910:a
1907:m
1903:t
1880:x
1877:a
1874:m
1870:t
1844:x
1841:a
1838:m
1834:t
1808:)
1805:x
1802:(
1797:k
1791:N
1756:x
1753:a
1750:m
1746:k
1735:x
1716:k
1704:x
1662:k
1656:N
1607:)
1600:x
1596:(
1593:f
1587:)
1584:x
1581:(
1578:f
1558:X
1552:)
1549:x
1546:(
1541:k
1531:N
1521:x
1501:)
1498:x
1495:(
1490:k
1484:N
1451:t
1448:p
1445:o
1441:x
1430:S
1412:)
1409:x
1406:(
1401:k
1391:N
1367:)
1364:x
1361:(
1356:k
1350:N
1322:x
1319:a
1316:m
1312:k
1308:,
1305:.
1302:.
1299:.
1296:,
1293:1
1290:=
1287:k
1284:,
1281:)
1278:x
1275:(
1270:k
1260:N
1243:x
1225:)
1222:x
1219:(
1214:k
1208:N
1185:)
1180:x
1177:a
1174:m
1170:k
1166:,
1163:.
1160:.
1157:.
1154:,
1151:1
1148:=
1145:k
1142:(
1137:k
1131:N
1088:)
1085:x
1082:(
1079:N
1071:i
1067:x
1056:x
1036:x
1019:x
960:L
956:x
935:)
930:L
926:x
922:(
919:N
896:X
890:)
885:L
881:x
877:(
874:N
866:x
858:,
855:)
852:x
849:(
846:f
840:)
835:L
831:x
827:(
824:f
799:L
795:x
750:X
742:x
734:,
725:)
720:h
716:x
712:(
709:f
705:/
701:)
698:)
695:x
692:(
689:f
683:)
678:h
674:x
670:(
667:f
664:(
639:h
635:x
611:X
603:x
595:,
586:)
577:x
573:(
570:f
566:/
562:)
559:)
556:x
553:(
550:f
544:)
535:x
531:(
528:f
525:(
503:X
495:x
487:,
481:+
478:)
475:x
472:(
469:f
463:)
454:x
450:(
447:f
418:x
394:=
391:X
363:X
355:x
347:,
344:)
341:x
338:(
335:f
329:)
320:x
316:(
313:f
289:X
277:x
249:n
245:R
241:=
238:S
227:S
219:f
215:x
211:X
207:S
189:}
186:S
180:X
177:,
174:X
168:x
164:|
160:)
157:x
154:(
151:f
148:{
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.