No description available.

In this paper we propose a hybrid approach for solving vehicle routing problems. The main idea is to combine an Ant System (AS) with a problem specific constructive heuristic, namely the well known Savings algorithm. This differs from previous approaches, where the subordinate heuristic was the Nearest Neighbor algorithm initially proposed for the TSP. We compare our approach with some other classic, powerful meta-heuristics and show that our results are competitive. / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

No description available.

No description available.

We present a hybrid optimization algorithm for mixed-integer linear programming, embedding both heuristic and exact components. In order to validate it we use the periodic vehicle routing problem (PVRP) as a case study. This problem consists of determining a set of minimum cost routes for each day of a given planning horizon, with the constraints that each customer must be visited a required number of times (chosen among a set of valid day combinations), must receive every time the required quantity of product, and that the number of routes per day (each respecting the capacity of the vehicle) does not exceed the total number of available vehicles. This is a generalization of the well-known vehicle routing problem (VRP). Our algorithm is based on the linear programming (LP) relaxation of a set-covering-like integer linear programming formulation of the problem, with additional constraints. The LP-relaxation is solved by column generation, where columns are generated heuristically by an iterated local search algorithm. The whole solution method takes advantage of the LP-solution and applies techniques of fixing and releasing of the columns as a local search, making use of a tabu list to avoid cycling. We show the results of the proposed algorithm on benchmark instances from the literature and compare them to the state-of-the-art algorithms, showing the effectiveness of our approach in producing good quality solutions. In addition, we report the results on realistic instances of the PVRP introduced in Pacheco et al. (2011) [24] and on benchmark instances of the periodic traveling salesman problem (PTSP), showing the efficacy of the proposed algorithm on these as well. Finally, we report the new best known solutions found for all the tested problems. (authors' abstract)

In this project the optimization of transport planning has been studied. The approach was that smaller transport companies do not have the capability to fully optimize their transports. Their transport optimization is performed at a company level, meaning that the end result might be optimal for their company, but that potential for further optimization exists. The idea was to build a collaboration of transport companies, and then to optimize the transports globally within the collaboration. The intent was for the collaboration to perform the same driving assignments but at a lower cost, by using fewer vehicles and drivers, or travel shorter distance, or both combined. This should be achieved by planning the assignments in a smarter way, for example using a company's empty return journey to perform an assignment for another company. Due to the complexity of these types of problems, called Vehicle Routing Problem (VRP), shown to be NP-complete, search methods are often used. In this project the method of choice was a PDDL-based planner called LPG-td. It uses enforced hill-climbing together with a best-first search to find feasible solutions. The method was tested for scaling, performance versus another method and against time, as well as together with a real-life based problem. The results showed that LPG-td might not be a suitable candidate to solve the problem considered in this project. The solutions found for the collaboration were worse than for the sum of individual solutions, and used more computational time. Since the solution for the collaboration at most should be equal to the sum of individual solutions, in theory, this meant that the planner failed.

The purpose of this research is to present the design and development of a routing system, custom developed for a fence manufacturing company in the continental US. The objective of the routing module of the system is to generate least cost routes from the home-center of the company to a set of delivery locations. Routes are evolved for a set of customer locations based on the sales order information and are frequently modified to include rush orders. These routes are such that each delivery is made within a given time window. Further, total truckload of all delivery locations over any particular route is not allowed to exceed the weight and volume capacities of the truck. The basic system modules such as user interface functions and database are designed using MS Access 2000. An interface module to retrieve data from existing ERP system of the company is developed to import pick-ticket information. A customer inter-distance maintenance module is designed with the abilities of a learning tool to reduce information retrieval time between the routing system and the GIS server. The Graphical User Interface with various screen forms and printable reports is developed along with the routing module to achieve complete system functionality and to provide an efficient logistics solution. This problem, formulated as a mixed-integer program, is of particular interest due to its generality to model problem scenarios in the production shop such as job-shop scheduling, material handling, etc. This problem is coded and solved for instances with different input parameters using AMPL/CPLEX. Results of test runs for the company data show that the solution time increases exponentially with the number of customers. Hence, a heuristic approach is developed and implemented. Sample runs with small instances are solved for optimality using AMPL/CPLEX and are used to compare the performance of the heuristics. However, test runs solved using the heuristics for larger instances are compared with the manual routing costs. The comparison shows a considerable cost savings for heuristic solutions. Further, a what-if analysis module is implemented to aid the dispatcher in choosing input parameters based on sensitivity analysis. In conclusion, further improvement of the routing system and future research directions are proposed.

Nowadays traffic congestion is a big problem all over the world. To solve this problem governments build broader roads, establish more reasonable traffic rules. Dynamic routing is a good and efficient way to reduce traffic congestion. That is why research of real time vehicle routing optimization algorithms was made. Experiment showed that best performance of shortest path algorithm was Dijkstra algorithm. Based on that, a software prototype was developed – optimized route search system. Driver can select shortest or fastest route to his destination. There was used roads length to evaluate shortest path and special coefficient to evaluate fastest route. This coefficient is calculated respectively to road load, length, speed limit, capacity. Performance of developed system is good so I conclude that the system is capable of routing vehicles in real time in complex traffic network.

Thesis (Ph. D.)--Lehigh University, 2005. / Includes vita. Includes bibliographical references (leaves 184-192).

In this paper we present and analyze the application of an Ant System to the Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW). At the core of the algorithm we use an Insertion procedure to construct solutions. We provide results on the learning and runtime behavior of the algorithm as well as a comparison with a custom made heuristic for the problem. / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"