| 1. |
- Westerlund, Andreas, 1974-, et al.
(författare)
-
A column generation scheme for the fixed fleet heterogeneous vehicle routing problem
- 2005
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We present an optimizing column generation procedure for solving the vehicle routing problem with a fixed heterogeneous fleet of vehicles; if the method is used in a truncated fashion it turns into a heuristic. The method is based on a new mathematical formulation, which includes a new type of valid inequalities, strengthened by the use of Chvátal-Gomory rounding, and a Lagrangian dualization of this formulation. The dual problem is attacked by subgradient optimization and a near-optimal dual solution obtained is used for enumerating routes that are promising candidates for being used in an optimal solution. These routes are collected in a set partitioning problem, which is finally solved, and an upper bound to the optimal objective value is obtained. The method is evaluated on a set of small-scale test instances. The valid inequalities improves the lower bound significantly: the improvement depends on the ratio between total customer demand and total vehicle capacity. The qualities of the upper bounds varies quite much among the instances.
|
|
| 2. |
- Westerlund, Andreas, 1974-, et al.
(författare)
-
A note on relatives to the Held and Karp 1-tree problem
- 2006
-
Ingår i: Operations Research Letters. - : Elsevier BV. - 0167-6377 .- 1872-7468. ; 34:3, s. 275-282
-
Tidskriftsartikel (refereegranskat)abstract
- We study a class of graph problems which includes as special cases the Held and Karp 1-tree problem, and the minimum spanning tree problem with one degree constraint studied by Glover and Klingman. For another special case, we note a mistake in a paper by Ramesh, Yoon and Karwan.
|
|
| 3. |
- Westerlund, Andreas, 1974-, et al.
(författare)
-
A stabilized column generation scheme for the traveling salesman subtour problem
- 2006
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 154:15, s. 2212-2238
-
Tidskriftsartikel (refereegranskat)abstract
- Given an undirected graph with edge costs and both revenues and weights on the vertices, the traveling salesman subtour problem is to find a subtour that includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour.We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented.
|
|
| 4. |
- Westerlund, Andreas, 1974-
(författare)
-
Accelerating column generation schemes : applications to routing problems
- 2005
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Many integer optimization problems of great practical importance are today attacked with column generation. Merits of column generation is that it enables the use of compact and flexible formulations of many complex optimization problems, and that it often gives rise to good (strong) formulations. A potential drawback with column generation is the well-known tailing-off phenomenon, that is, that the objective value is improved rapidly in early iterations but very slowly in the late iterations.We study various techniques for accelerating column generation methods for (integer) linear programs. We evaluate the use of stabilized column generation on a Traveling Salesman Subtour Problem, TSSP, a problem which is closely related to the Prize Collecting Traveling Salesman Problem. We further study how subgradient optimization can be used with the purpose of predicting optimal columns (and, optionally, non-binding restrictions). This technique is tested on the TSSP and the multicommodity network flow problem.Another idea evaluated in this thesis is the use of over-generation of columns in a column generation scheme for an integer programming problem, in this case a vehicle routing problem with a heterogeneous fleet of vehicles.The thesis also includes a note on a class of relatives to the Held and Karp 1–tree problem. It is shown that two subclasses have polynomial time-complexity. Further, we note a mistake in an earlier work and provide a counter-example to the erroneous result.
|
|
| 5. |
- Westerlund, Andreas, 1974-
(författare)
-
Decomposition schemes for the traveling salesman subtour problem
- 2002
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Given an undirected graph with edge costs and both revenues and weights on the vertices, the Traveling Salesman Subtour Problem is to find a subtour that passes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour. This problem generalizes the Traveling Salesman Problem and is therefore -hard. The Traveling Salesman Subtour Problem and its relatives are of interest in themselves, and they also arise as subproblems in various contexts.We present a new and strong formulation, which is inspired by the classic side-constrained 1-tree formulation of the Traveling Salesman Problem. Here, the side constraints comprise vertex degree restrictions, a knapsack constraint and variable upper bound (VUB) constraints. In our solution approaches, these side constraints are Lagrangian relaxed. The relaxed problem is transformed, via a simple variable substitution, into the problem of finding a minimum cost degree-constrained 1-tree in an expanded graph.The Lagrangian dual problem is attacked with subgradient optimization and a cutting plane scheme. The latter is implemented in its dually equivalent form, that is, as a column generation scheme. The column generation procedure is stabilized by restricting the dual variables to stay inside a box around the current dual iterate; this technique is a slight modification of the so called boxstep method. Further, a combined algorithm is presented. This combination inherits the advantages of subgradient optimization and column generation, and it aims to avoid their respective drawbacks.An important conclusion from our work is that the use of the VUB constraints significantly improves the quality of the lower bounds, although they are redundant in the integer programming formulation. We also conclude that the stabilizing technique is crucial for obtaining computational efficiency in the column generation scheme. Finally, it is established that it might be very advantageous to use the subgradient optimization procedure as a means for initiating the column generation scheme.
|
|
| 6. |
|
|
| 7. |
- Westerlund, Andreas, 1974-, et al.
(författare)
-
Subgradient optimization prior to column generation : a means for predicting optimal columns (and non-binding restrictions)
- 2005
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Many classes of combinatorial and mixed integer optimization problems are attacked with decomposition methods. One technique is to perform subgradient optimization on a Lagrangean dual problem: another is to perform column generation on a Dantzig-Wolfe problem, or equivalently, cut generation on its linear programming dual. These techniques both have advantages and disadvantages. In this paper these techniques are combined into a two-phase method, with the purpose of overcoming drawbacks of the techniques.The two-phase method consists of a prediction phase and a solution phase. In the prediction phase, subgradient optimization is performed: subgradients found are stored and used as starting columns for the solution phase. (Optionally, non-binding restricitions can be predicted based on information from the prediction phase.) The columns found are used to construct a Dantzig/Wolfe master problem. In the solution phase, column generation is performed if needed. A solid theoretical bases for the two-phase method is presented which includes strong asymptotical results. ln practise, truncated usage must be performed: practical guidelines are given in the paper.The two-phase method is tested on two applications: a multicommodity network flow problem and a convexified version of the traveling salesman subtour problem. Two categories of numerical experiments are presented. ln the first category, various aspects of truncated usage of the theory are illustrated. In the second category, the two-phase method is tested on a relatively large number of test problems.An overall conclusion of our work is that the two-phase method can perform significantly better, in terms of CPU-times, compared to a (stabilized) Dantzig-Wolfe algorithm. ln general, whenever the subproblems are computationaly inexpensive, compared to the Dantzig-Wolfe master programs, the two-phase method might be an interesting alternative to use instead of pure Dantzig-Wolfe.
|
|
| 8. |
|
|
