共查询到20条相似文献,搜索用时 15 毫秒
1.
Fabien Tricoire 《4OR: A Quarterly Journal of Operations Research》2007,5(2):165-168
We present an overview of the author’s Ph.D. thesis, supervised by P. Dejax and N. Bostel, which was defended in February
2006 at école des Mines de Nantes, France. The thesis is written in French, and is available at . It was conducted in the context of a research contract with a water distribution company. In a first section, we define
multiperiod routing problems for service technicians. In a second section, we present some heuristics and a memetic algorithm
used to solve these problems. The third section introduces optimal and near-optimal approaches based on column generation.
Finally, we present some applications to the real-life case. The methods presented in Sects. 2, 3 and 4 were tested over several
sets of problems, based on real-life statistics provided by the company.
相似文献
2.
Performances improvement of the column generation algorithm: application to vehicle routing problems
Nora Touati Moungla 《4OR: A Quarterly Journal of Operations Research》2010,8(2):217-220
We survey the main results obtained by the author in his PhD dissertation supervised by Anass Nagih and Lucas Létocart. It
was defended in December 2008 at The Computer Science lab of the Paris-Nord University (L.I.P.N.), Villetaneuse, France. The
thesis is written in French and is available from . Column generation algorithms are instrumental in many areas of applied optimization, where linear programs with an enormous
number of variables need to be solved. Although successfully used in many applications, this method suffers from well-known
“instability” issues that somewhat limit its efficiency. This work focuses on accelerating strategies in a column generation
scheme; on the first iterations using diversification, on the last iterations using reoptimization and on the overall GC scheme
using an improving technique to solve the pricing problems (dynamic programming with blocs). The effectiveness of these approaches
is validated on the Vehicle Routing Problem with Time Windows. 相似文献
3.
Andrea Tramontani 《4OR: A Quarterly Journal of Operations Research》2011,9(3):325-328
This is a summary of the author’s PhD thesis supervised by Andrea Lodi and Paolo Toth and defended on 16 April 2009 at the
Università di Bologna. The thesis is written in English and is available from the author upon request. This work is focused
on Mixed Integer Programming (MIP). In particular, the first part of the thesis deals with general purpose cutting planes,
which are probably the key ingredient behind the success of the current generation of MIP solvers. The second part is instead
focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems
in the context of routing applications. 相似文献
4.
Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem
The routing and wavelength assignment (RWA) problem typically occurs in wavelength division multiplexing optical networks. Given a number of available wavelengths, we consider here the problem of maximising the number of accepted connections with respect to the clash and continuity constraints. We first propose a new strategy which combines two existing models. This leads to an improved column generation scheme. We also present two heuristics to compute feasible solutions: a hybrid heuristic and the integer solution at the root node of the column generation. Our approaches are compared with the best existing results on a set of classic RWA instances. 相似文献
5.
6.
This paper summarizes the main results presented by the author in his PhD thesis (Montoya-Torres 2005), supervised by Stéphane
Dauzèere-Pérés, Jean-Pierre Campagne and Hélène Marian, and defended on 29 November 2005 at the école des Mines de Saint-étienne
and Université Jean-Monnet. The thesis is written in French and is available upon request from the author. This work deals
with a real-life transportation problem in the semiconductor industry. It proposes a new approach by integrating tactical
and operational decisions for the control of the automated transport system. At the tactical level, the problem is modeled
using integer linear programming models inspired from Location Theory. At the operational level, the solution obtained from
the tactical optimization is coupled with a discrete-event computer simulation program and some policies for transportation
operations are implemented and compared. 相似文献
7.
Sana Belmokhtar 《4OR: A Quarterly Journal of Operations Research》2008,6(3):315-318
The paper summarizes the main results of the author’s Ph.D. thesis presented in December 2006 at the école des Mines de Saint
étienne. The work was supervised by Alexandre Dolgui and Xavier Delorme. The thesis is written in French and is available
upon request from the author. Its purpose is to provide decision support in the design and reconfiguration of modular machining
lines with multi-spindle units. This design problem is defined as the selection of spindle units to perform a set of operations
needed to produce the parts and subsequently their assignment to workstations. The corresponding optimization problem is solved
using different models based on integer and constraint programming.
相似文献
8.
B. Escoffier 《4OR: A Quarterly Journal of Operations Research》2007,5(2):161-164
This is a summary of the most important results of the author’s PhD thesis. This thesis, supervised by Vangelis Th. Paschos,
was defended in October 2005 at the Université Paris Dauphine. It is written in French and is available on-line. The thesis is focused on combinatorial optimization problems, studied
from the standpoint of polynomial approximation theory. We were interested both in structural concerns (mainly completeness
in approximation classes and logical expressivity) and operational ones (with the study of satisfiability, coloring and covering
problems).
http://www.lamsade.dauphine.fr/~escoffier/fichiers/TheseEscoffier.pdf 相似文献
9.
Arnaud Liefooghe 《4OR: A Quarterly Journal of Operations Research》2011,9(2):219-222
This is a summary of the author’s PhD thesis supervised by Laetitia Jourdan and El-Ghazali Talbi and defended on 8 December
2009 at the Université Lille 1. The thesis is written in French and is available from . This work deals with the design, implementation and experimental analysis of metaheuristics for solving multiobjective optimisation
problems, with a particular interest on hard and large combinatorial problems from the field of logistics. After focusing
on a unified view of multiobjective metaheuristics, we propose new cooperative, adaptive and parallel approaches. The performance
of these methods are experimented on a scheduling and a routing problem involving two or three objective functions. We finally
discuss how to adapt such metaheuristics during the search process in order to handle uncertainty that may occur from many
different sources. 相似文献
10.
Cédric Bentz 《4OR: A Quarterly Journal of Operations Research》2008,6(1):89-92
This is a summary of the author’s PhD thesis supervised by Marie- Christine Costa and Frédéric Roupin and defended on 20 November
2006 at the Conservatoire National des Arts et Métiers in Paris (France). The thesis is written in French and is available
upon request from the author. This work deals with two well-known optimization problems from graph theory: the maximum integral
multiflow and the minimum multicut problems. The main contributions of this thesis concern the polynomial-time solvability
and the approximation of these two problems (and of some of their variants) in classical classes of graphs: bounded tree-width
graphs, planar graphs and grids, digraphs, etc.
相似文献
11.
Mourad Boudia 《4OR: A Quarterly Journal of Operations Research》2008,6(1):93-96
This is a summary of the main results presented in the author’s Ph.D thesis, supervised by C. Prins and defended at the Université
de Technologie de Troyes in October 2006. The thesis, written in French, is available from the author upon request. It deals
with the integrated optimization of production planning and distribution in supply chains. A single product case and a multiproduct
case are investigated. Integer linear programming models are proposed and different approaches based on heuristics, metaheuristics
and cooperative methods are developed. Significant savings are obtained, compared to classical decoupled methods. These results
confirm both the interest of integrating production and distribution decisions and of using metaheuristics for the largest
instances.
相似文献
12.
The periodic vehicle routing problem (PVRP) consists in establishing a planning of visits to clients over a given time horizon so as to satisfy some service level while optimizing the routes used in each time period. The tactical planning model considered here restricts its attention to scheduling visits and assigning them to vehicles while leaving sequencing decisions for an underlying operational model. The objective is twofold: to optimize regional compactness of the routes in a desire to specialize routes to restricted geographical area and to balance the workload evenly between vehicles. Approximate solutions are constructed using a truncated column generation procedure followed by a rounding heuristic. This mathematical programming based procedure can deal with problems with 50–80 customers over five working days which is the range of size of most PVRP instances treated in the literature with meta-heuristics. The paper highlights the importance of alternative optimization criteria not accounted for in standard operational models and provides insights on the implementation of a column generation based rounding heuristic. 相似文献
13.
This paper studies an arc routing problem with capacity constraints and time-dependent service costs. This problem is motivated by winter gritting applications where the “timing” of each intervention is crucial. The exact problem-solving approach reported here first transforms the arc routing problem into an equivalent node routing problem. Then, a column generation scheme is used to solve the latter. The master problem is a classical set covering problem, while the subproblems are time-dependent shortest path problems with resource constraints. These subproblems are solved using an extension of a previously developed algorithm. Computational results are reported on problems derived from a set of classical instances of the vehicle routing problem with time windows. 相似文献
14.
Marie-Christine Plateau 《4OR: A Quarterly Journal of Operations Research》2008,6(2):187-190
This is a summary of the author’s PhD thesis supervised by A. Billionnet and S. Elloumi and defended on November 2006 at the
CNAM, Paris (Conservatoire National des Arts et Métiers). The thesis is written in French and is available from http://www.cedric.cnam.fr/PUBLIS/RC1115.
This work deals with exact solution methods based on reformulations for quadratic 0–1 programs under linear constraints. These
problems are generally not convex; more precisely, the associated continuous relaxation is not a convex problem. We developed
approaches with the aim of making the initial problem convex and of obtaining a good lower bound by continuous relaxation.
The main contribution is a general method (called QCR) that we implemented and applied to classical combinatorial optimization
problems.
相似文献
15.
Wassila Ouerdane 《4OR: A Quarterly Journal of Operations Research》2011,9(4):429-432
This is a summary of the Ouerdane’s PhD thesis supervised by Alexis Tsoukiàs and Nicolas Maudet and defended on 01 December
2009 at the Université Paris-Dauphine, Paris. The thesis is written in English and is available from the author upon request.
This work has the aim to investigate the different ways to use argumentation theory in a decision context. More precisely
within multi-criteria evaluation models. The principal aim is to meet the needs in terms of explanations and revision during
a decision process. 相似文献
16.
Manuel Iori 《4OR: A Quarterly Journal of Operations Research》2005,3(2):163-166
We present the main results in the author’s Ph.D. thesis (Iori 2004), defended at the University of Bologna in April 2004 and supervised by S. Martello. The thesis is written in English and is available from the author upon request. It proposes exact and metaheuristic algorithms for solving some relevant combinatorial optimization problems, with particular emphasis on scheduling, two-dimensional cutting and packing and capacitated vehicle routing. The performance of each algorithm is tested through extensive computational experiments and comparison with other approaches in the literature.Received: 21 September 2004, AMS classification:
90-08, 90C27, 90C59 相似文献
17.
Makhlouf Hadji 《4OR: A Quarterly Journal of Operations Research》2013,11(2):197-198
This is a summary of my PhD thesis supervised by Walid Ben-Ameur and defended on September 29 2009, at Télécom SudParis. The thesis is written in French language and is available from the author upon request at makhlouf.hadji@it-sudparis.eu. 相似文献
18.
Louis-Martin Rousseau Michel Gendreau Gilles Pesant Filippo Focacci 《Annals of Operations Research》2004,130(1-4):199-216
Constraint programming based column generation is a hybrid optimization framework recently proposed (Junker et al., 1999) that uses constraint programming to solve column generation subproblems. In the past, this framework has been used to solve scheduling problems where the associated graph is naturally acyclic and has done so very efficiently. This paper attempts to solve problems whose graph is cyclic by nature, such as routing problems, by solving the elementary shortest path problem with constraint programming. We also introduce new redundant constraints which can be useful in the general framework. The experimental results are comparable to those of the similar method in the literature (Desrochers, Desrosiers, and Solomon, 1992) but the proposed method yields a much more flexible approach. 相似文献
19.
Chefi Triki Simona Oprea Patriza Beraldi Teodor Gabriel Crainic 《European Journal of Operational Research》2014
In this paper, we deal with the generation of bundles of loads to be submitted by carriers participating in combinatorial auctions in the context of long-haul full truckload transportation services. We develop a probabilistic optimization model that integrates the bid generation and pricing problems together with the routing of the carrier’s fleet. We propose two heuristic procedures that enable us to solve models with up to 400 auctioned loads. 相似文献
20.
S. Zlobec 《Mathematical Programming》1985,31(3):245-268
Mathematical models are considered as input-output systems. The input is data (technological coefficients, available energy,
prices) and the output is the feasible set, the set of optimal solutions, and the optimal value. We study when output is a
continuous function of input and identify optimal (minimal) realizations of mathematical models. These are states of the model
having the property that every stable perturbation of input results in a locally worse (higher) value of the optimal value
function. In input optimization we “optimize” mathematical model rather than a specific mathematical program.
This research was supported in part by the Natural Sciences and Engineering Research Council of Canada, and in part by the
Gouvernement du Québec, programme de formation de chercheurs et d’action concertée. 相似文献