Confira o tema da conferência de David Applegate

Using large-scale computation to estimate the Beardwood-Halton-Hammersley TSP constant

In 1959, J. Beardwood, J. H. Halton, and J. M. Hammersley proved that the expected length L_n of the Traveling Salesman tour through n points uniformly distributed in the unit square is assymptotic to \Beta sqrt(n) as n goes to infinity, for some constant \Beta. However, their theorem didn't give the value of \Beta, only that it existed. They also gave a rough estimate that \Beta was about 0.75. Since then, there have been a number of attempts to derive better estimates of \Beta. I will discuss some recent large-scale computatoins using Concorde, our TSP solver, to obtain a new estimate of \Beta, as well as some experiments aimed at determining what properties of the TSP and of the unit square have the largest impact on the convergence to \Beta sqrt(n). This is joint work with William Cook, David S. Johnson, and Neil J. A. Sloane.

Confira o tema da Conferência de Stewart Robinson

Modelagem de Serviço de Operações: Uma abordagem de Simulação de evento-discreto e Agente Base.

Stewart Robinson, Operational Research and Management Sciences Group, Warwick Business School, University of Warwick, Coventry, CV4 7AL, United Kingdom

Simulação de evento-discreto, o qual se perdeu com o modelo de sistemas de manufaturas, tem sido crescentemente aplicado no setor de serviços. A abordagem, entretanto, nem sempre é apropriada ao modelo de operação de serviços. Em particular, não pode ajudar com decisões detalhadas sobre o layout dos serviços operacionais nos quais os clientes estão presentes, bem como varejos e aeroportos. A abordagem de simulação de evento-discreto e agente-base é proposta para modelagem enquanto sistemas. A abordagem deverá ser feita através do simples modelo de uma cafeteria. Extensões da Abordagem também serão discutidas.


Stewart Robinson é Professor de Pesquisa Operacional e Diretor Associado no Specialist Masters Programmes na Warwick Business School. Anteriormente empregado na consultoria de simulações, apoiou o uso da simulação em companhias na Europa e no resto do mundo. É autor e co-autor de quatro livros da área. Suas pesquisas focam na prática de desenvolvimento e uso do modelo de simulação. Áreas-chave de interesse são modelagem conceitual, validação de modelos, análise de rendimento e modelos alternativos de simulação (evento-discreto, sistemas dinâmicos e agente base. Também é co-editor do Journal of Simulation e Vice-Presidente da Sociedade de Pesquisa Operacional do Reino Unido.

Confira o tema da Conferência de Arne Lokketangen

Rich Vehicle Routing Problems - some examples


This presentation will look at some recent rich (real-world based) vehicle routing problems that the author has worked on. These all are based on the standard CVRP, but with the addition of some (real-world) constraints, making classical solution methods unsuitable. Our set of examples contains sequence dependent loading capacity, routing with inventory constraints, a stochastic routing problem where some historic data are available to be used as predictors, dynamic routing requests and a novel approach for the dynamic online case where the search quality is dependent on the current problem request frequency.
All the examples are based on real-world problems, and are generally solved using real-world data. The solution methods are mostly based on tabu search, but usually with some extra refinements.
We also would like to emphasize that the additional effort needed to solve these types of problems is readily compensated by the resulting quality and usefulness of the generated solutions.

Confira o tema da Conferência de Michel Gendreau

Recent Advances in Stochastic Vehicle Routing

Michel Gendreau
École Polytechnique de Montréal

While Vehicle Routing Problems have now been studied extensively for more than 50 years, those in which some parameters are uncertain at the time where the routes are made have received significantly less attention, in spite of the fact that there are many real-life settings where key parameters are not known with certainty. In this talk, after a short introduction to the various classes of Stochastic Vehicle Routing Problems and a brief survey of existing work in the area, we will focus on two problems on which we are currently working: the Vehicle Routing Problem with Stochastic Demands (VRPSD) and the Consistent Vehicle Routing Problem (CVRP).

The VRPSD consists in finding tours for a fleet of capacitated vehicles delivering goods to a set of customers with stochastic demands. A key feature of the problem is that the cumulative demand of the customers assigned to a vehicle may turn out to exceed its capacity, a situation defined as a route failure. The traditional approach to deal with failures is to send the involved vehicle back to the depot to replenish its stock whenever a failure is detected. These trips back to the depot increase the length of the routes effectively performed by the vehicles. The objective in the VRPSD is to find the set of routes that yields the lowest expected total cost when these trips to the depot are considered. We will present a new exact algorithm for the VPRSD, based on the Integer L-shaped method and new families of valid inequalities. Computational results on a set of small to medium benchmark instances will be reported and discussed.

The Consistent Vehicle Routing Problem (CVRP) is a problem that was recently proposed by Bruce Golden and his coauthors. The situation considered is that of express mail delivery companies, such as UPS, who would like to provide their regular commercial customers with consistent service, in the sense that they would like to visit them every day around the same time, if they need service. We propose to model this problem as variant of the Vehicle Routing Problem with Stochastic Customers (VRPSC), in which one must decide both the sequence in which customers will be visited by each vehicle and a target time for each visit. For each visited customer on a given day, consistency is measured as a deviation from its target time. The overall objective is to minimize the sum of expected travel costs and deviations. An exact solution approach will be described and preliminary computational results on small instances will be presented.

(Joint work with Walter Rei, Ola Gabali and Tom Van Woensel).

Confira o tema da Conferência de Gilbert Laporte

The Vehicle Routing Problem

Gilbert Laporte
Canada Research Chair in Distribution Management
HEC montreal, Canada

The Vehicle Routing Problem is central to distribution management. This problem has attracted the attention of operations researchers for more than fifty years, but remains very difficult to solve to optimality. In this talk, I will survey the evolution of the main exact and metaheuristic algorithms for this important problem. Comparative computational results will be reported.
Website melhor visualizado nos navegadores Mozilla Firefox e Chrome.