Skip to main navigationSkip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

CORMSIS Seminar Event

Time:
16:00 - 17:00
Date:
5 February 2015
Venue:
Room 02/3041

For more information regarding this event, please email Edgar Possani at epossani@itam.mx .

Event details

The Cross-Entropy Method with applications to vehicle routing problems

Abstract:

The Cross-Entropy Method (CEM) was initially developed to estimate rare event probabilities through simulation, but can be modified, and has recently been applied to some combinatorial optimization problems. We will give a brief introduction to the CEM with the particular focus on its viability to solve vehicle routing problems (VRPs). Published implementations have considered a naive route-splitting scheme over a limited set of instances. We have implemented a dynamic programming route-splitting algorithm that is better, and also designed a novel cluster-first/route-second approach. We suggest improvements on the convergence of CEM, and will present computational results to evaluate these approaches. Finally we will discuss the advantages and drawbacks of using CEM for this type of problems.

Speaker information

Prof. Edgar Possani,ITAM (Instituto Tecnologico Autonomo de Mexico), About the speaker: Prof. Edgar Possani obtained a PhD in Mathematics from the University of Southampton in 2001. He was research fellow at the Management School (2001-2003) on an EPSRC funded project to do with operational and financial decision of start-up companies. From 2003 until 2005 he worked for the Mexican Institute of Petroleum where he undertook several project to do with transport and logistics in oil exploration, and evaluation of R&D projects. Since 2006 he is a member of the Department of Mathematics at the Instituto Tecnológico Autónomo de México (ITAM) in Mexico City, where he became associate and full professor in 2008 and 2011 respectively. He has worked on different projects using a variety of OR techniques to include scheduling of operations in manufacturing companies, stochastic modeling using Markov Decision processes, project evaluation using data envelopment analysis, and heuristic design for vehicle routing problems. He is currently undertaking a year sabbatical at Southampton Business School.

Privacy Settings