共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
Karim Labadi 《4OR: A Quarterly Journal of Operations Research》2008,6(4):407-410
This is a summary of the author’s PhD thesis supervised by Lionel Amodeo and Hoaxun Chen and defended on 29 November 2005 at
the Université de Technologie de Troyes (France). The thesis is written in French and is available from the author upon request.
This work deals with a new stochastic Petri net model and its applications for modeling and studying logistics systems and
more generally discrete event dynamic systems.
相似文献
3.
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.
相似文献
4.
Patrick Meyer 《4OR: A Quarterly Journal of Operations Research》2009,7(2):191-194
This is a summary of the author’s Ph.D. thesis, defended on 8 October 2007 at the University of Luxembourg and the Faculté
Polytechnique de Mons, under the joint supervision of Raymond Bisdorff and Marc Pirlot. The thesis is written in English and
is available from the author upon request. The work is situated in the field of multiple criteria decision analysis. It mostly
deals with what we call progressive methods, i.e., iterative procedures presenting partial conclusions to the decision maker that can be refined at further steps of
the analysis. Such progressive methods have been studied in the context of multiattribute value theory and outranking methods.
相似文献
5.
We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for the VRP with stochastic demands require independent demands. We first study an edge-based formulation for the CCVRP, in particular addressing the challenge of how to determine a lower bound on the number of vehicles required to serve a subset of customers. We then investigate the use of a branch-and-cut-and-price (BCP) algorithm. While BCP algorithms have been considered the state of the art in solving the deterministic VRP, few attempts have been made to extend this framework to the VRP with stochastic demands. In contrast to the deterministic VRP, we find that the pricing problem for the CCVRP problem is strongly \(\mathcal {NP}\)-hard, even when the routes being priced are allowed to have cycles. We therefore propose a further relaxation of the routes that enables pricing via dynamic programming. We also demonstrate how our proposed methodologies can be adapted to solve a distributionally robust CCVRP problem. Numerical results indicate that the proposed methods can solve instances of CCVRP having up to 55 vertices. 相似文献
6.
We examine neighborhood structures for heuristic search applicable to a general class of vehicle routing problems (VRPs). Our methodology utilizes a cyclic-order solution encoding, which maps a permutation of the customer set to a collection of many possible VRP solutions. We identify the best VRP solution in this collection via a polynomial-time algorithm from the literature. We design neighborhoods to search the space of cyclic orders. Utilizing a simulated annealing framework, we demonstrate the potential of cyclic-order neighborhoods to facilitate the discovery of high quality a priori solutions for the vehicle routing problem with stochastic demand (VRPSD). Without tailoring our solution procedure to this specific routing problem, we are able to match 16 of 19 known optimal VRPSD solutions. We also propose an updating procedure to evaluate the neighbors of a current solution and demonstrate its ability to reduce the computational expense of our approach. 相似文献
7.
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. 相似文献
8.
In this paper we use Monte Carlo Techniques to deal with a real world delivery problem of a food company in Valencia (Spain).
The problem is modeled as a set of 11 instances of the well known Vehicle Routing Problem, VRP, with additional time constraints.
Given that VRP is a NP-hard problem, a heuristic algorithm, based on Monte Carlo techniques, is implemented. The solution
proposed by this heuristic algorithm reaches distance and money savings of about 20% and 5% respectively.
This work has been partially supported by thePlan de Incentivo a la Investigación/98 of the Universidad Politécnica de Valencia, under the project “Técnicas Monte Carlo aplicadas a Problemas de Rutas de Vehículos”. 相似文献
9.
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.
相似文献
10.
A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm 总被引:2,自引:0,他引:2
Yannis Marinakis Athanasios Migdalas Panos M. Pardalos 《Journal of Global Optimization》2007,38(4):555-580
The Vehicle Routing Problem (VRP) is one of the most well studied problems in operations research, both in real life problems
and for scientific research purposes. During the last 50 years a number of different formulations have been proposed, together
with an even greater number of algorithms for the solution of the problem. In this paper, the VRP is formulated as a problem
of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility
of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles
will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision
maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment
is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of
customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population
and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory
results. In both sets of instances the average quality is less than 1%. More specifically in the set with the 14 classic instances
proposed by Christofides, the quality is 0.479% and in the second set with the 20 large scale vehicle routing problems, the
quality is 0.826%. The algorithm is ranked in the tenth place among the 36 most known and effective algorithms in the literature
for the first set of instances and in the sixth place among the 16 algorithms for the second set of instances. The computational
time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact
that the Expanding Neighborhood Search Strategy is used. 相似文献
11.
The well-known vehicle routing problem (VRP) has been studied in depth over the last decades. Nowadays, generalizations of VRP have been developed for tactical or strategic decision levels of companies but not both. The tactical extension or periodic VRP (PVRP) plans a set of trips over a multiperiod horizon, subject to frequency constraints. The strategic extension is motivated by interdependent depot location and routing decisions in most distribution systems. Low-quality solutions are obtained if depots are located first, regardless of the future routes. In the location-routing problem (LRP), location and routing decisions are tackled simultaneously. Here for the first time, except for some conference papers, the goal is to combine the PVRP and LRP into an even more realistic problem covering all decision levels: the periodic LRP or PLRP. A hybrid evolutionary algorithm is proposed to solve large size instances of the PLRP. First, an individual representing an assignment of customers to combinations of visit days is randomly generated. The evolution operates through an Evolutionary Local Search (ELS) on visit day assignments. The algorithm is hybridized with a heuristic based on the Randomized Extended Clarke and Wright Algorithm (RECWA) to create feasible solutions and stops when a given number of iterations is reached. The method is evaluated over three sets of instances, and solutions are compared to the literature on particular cases such as one-day horizon (LRP) or one depot (PVRP). This metaheuristic outperforms the previous methods for the PLRP. 相似文献
12.
An exact algorithm for team orienteering problems 总被引:1,自引:1,他引:0
Sylvain Boussier Dominique Feillet Michel Gendreau 《4OR: A Quarterly Journal of Operations Research》2007,5(3):211-230
Optimising routing of vehicles constitutes a major logistic stake in many industrial contexts. We are interested here in the
optimal resolution of special cases of vehicle routing problems, known as team orienteering problems. In these problems, vehicles
are guided by a reward that can be collected from customers, while the length of routes is limited. The main difference with
classical vehicle routing problems is that not all customers have to be visited. The solution method we propose here is based
on a Branch & Price algorithm. It is, as far as we know, the first exact method proposed for such problems, except for a preliminary
work from Gueguen (Methodes de résolution exacte pour problémes de tournées de véhicules. Thése de doctorat, école Centrale
Paris 1999) and a work from Butt and Ryan (Comput Oper Res 26(4):427–441 1999). It permits to solve instances with up to 100
customers.
相似文献
13.
Joaquín L. Fernández Rafael Sanz Reid G. Simmons Amador R. Diéguez 《Journal of Heuristics》2006,12(3):181-209
This paper proposes a set of methods for solving stochastic decision problems modeled as partially observable Markov decision
processes (POMDPs). This approach (Real Time Heuristic Decision System, RT-HDS) is based on the use of prediction methods combined with several existing heuristic decision algorithms. The prediction process
is one of tree creation. The value function for the last step uses some of the classic heuristic decision methods. To illustrate
how this approach works, comparative results of different algorithms with a variety of simple and complex benchmark problems
are reported. The algorithm has also been tested in a mobile robot supervision architecture. 相似文献
14.
N A Wassan 《The Journal of the Operational Research Society》2006,57(1):111-116
The classical vehicle routing problem (VRP) involves determining a fleet of homogeneous size vehicles and designing an associated set of routes that minimizes the total cost. Our tabu search (TS) algorithm to solve the VRP is based on reactive tabu search (RTS) with a new escape mechanism, which manipulates different neighbourhood schemes in a very sophisticated way in order to get a balanced intensification and diversification continuously during the search process. We compare our algorithm with the best methods in the literature using different data sets and report results including new best known solutions for several well-known benchmark problems. 相似文献
15.
Methods to solve multi-skill project scheduling problem 总被引:2,自引:0,他引:2
This is a summary of the author’s PhD thesis supervised by P. Martineau and E. Néron and defended on 28 November 2006 at the Université François-Rabelais de Tours. The thesis is written in French, and is available upon request from the author. This work deals with the problem of scheduling a project. The activities of this project requires skills that may not be mastered by all persons involved. First of all, the problem is defined in the introduction part. Then we propose different methods to solve it: lower bounds in part 2, different heuristics and meta-heuristics in part 3, and finally a branch-and-bound procedure in the last part. 相似文献
16.
The vehicle routing problem (VRP), a well-known combinatorial optimization problem, holds a central place in logistics management. This paper proposes an improved ant colony optimization (IACO), which possesses a new strategy to update the increased pheromone, called ant-weight strategy, and a mutation operation, to solve VRP. The computational results for fourteen benchmark problems are reported and compared to those of other metaheuristic approaches. 相似文献
17.
Cyril Canon 《4OR: A Quarterly Journal of Operations Research》2007,5(1):89-92
We discuss the main results of the author’s PhD thesis (Canon 2005) presented in December 2005 at the Université François-Rabelais de Tours and supervised by J.-C. Billaut and J.-L. Bouquard. This thesis is written in French and is available from the author upon request. It deals with three different problems arising in the call center industry: the problem of dimensioning a call center, the annualisation problem and finally the Shift Design Problem. 相似文献
18.
Roberto Baldacci Enrico Bartolini Aristide Mingozzi Roberto Roberti 《Computational Management Science》2010,7(3):229-268
This paper presents an exact solution framework for solving some variants of the vehicle routing problem (VRP) that can be
modeled as set partitioning (SP) problems with additional constraints. The method consists in combining different dual ascent
procedures to find a near optimal dual solution of the SP model. Then, a column-and-cut generation algorithm attempts to close
the integrality gap left by the dual ascent procedures by adding valid inequalities to the SP formulation. The final dual
solution is used to generate a reduced problem containing all optimal integer solutions that is solved by an integer programming
solver. In this paper, we describe how this solution framework can be extended to solve different variants of the VRP by tailoring
the different bounding procedures to deal with the constraints of the specific variant. We describe how this solution framework
has been recently used to derive exact algorithms for a broad class of VRPs such as the capacitated VRP, the VRP with time
windows, the pickup and delivery problem with time windows, all types of heterogeneous VRP including the multi depot VRP,
and the period VRP. The computational results show that the exact algorithm derived for each of these VRP variants outperforms
all other exact methods published so far and can solve several test instances that were previously unsolved. 相似文献
19.
Moshe Dror Gilbert Laporte Francois V. Louveaux 《Mathematical Methods of Operations Research》1993,37(3):273-283
This paper considers a class of stochastic vehicle routing problems (SVRPs) with random demands, in which the number of potential failures per route is restricted either by the data or the problem constraints. These are realistic cases as it makes little sense to plan vehicle routes that systematically fail a large number of times. First, a chance constrained version of the problem is considered which can be solved to optimality by algorithms similar to those developed for the deterministic vehicle routing problem (VRP). Three classes of SVRP with recourse are then analyzed. In all cases, route failures can only occur at one of the lastk customers of the planned route. Since in general, SVRPs are considerably more intractable than the deterministic VRPs, it is interesting to note that these realistic stochastic problems can be solved as a sequence of deterministic traveling salesman problems (TSPs). In particular, whenk=1 the SVRP with recourse reduces to a single TSP. 相似文献
20.
Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods. 相似文献