Monday, February 15th, 2010
Vehicle Routing Problem(VRP) is actually a generalization of Traveling Salesman Problem. In most basic model, we have a depot and customers are distrubeted on the plane. Each customer has a different demand. We have capacitated vehicles in the depot. Our aim is to minimize total distance traveled by our vehicles by considering some constraints. I recommend this book for a fresh, good start to VRP. I developped a web application called AR-RO which uses Google Maps API. The main contribution is that distances are real, which is not true in the literature. Moreover, instances generated can be saved on a XML file and be used in a different platform. This presentation file contains detailed information about AR-RO.
Tags: Network Models, Web based User Interfaces, XML
Posted in Optimization | No Comments »
Friday, February 12th, 2010
Traveling Salesman Problem also known as TSP can be defined as follows: Given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city. This is a good book about TSP. You can find TPS instances in this site. These instances can be used in order to benchmark algorithms. In this report some contructive heuristic methods (nearest neighbor, arbitrary insertion, farthest insertion) as well as a improvement heuristic (2-opt) are compared. Corresponding matlab files are also available.
Tags: Heuristic Methods, Matlab, Network Models
Posted in Optimization | No Comments »