Analysis of heuristic algorithms for rich vehicle routing problems

Author(s)

Peterson Katagiri Zilli

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2011-05-13

Examining board members

Cid Carvalho de Souza; Celso da Cruz Carneiro Ribeiro; Flávio Keidi Miyazawa

• Advisor: Cid Carvalho de Souza

Abstract

The Vehicle Routing Problem (VRP) was first proposed by Dantzig and Ramser in 1959 and, since then, a large number of papers has been devoted to the solution of its variants. The original problem consists in determining an optimal set of routes to be used by vehicles of limited capacity that serve a set of customers. In this paper we focus on the study and implementation of models called "rich" in the literature, which include complex variants of the VRP that represent situations closer to the logistical problems encountered in real distribution systems. The main motivation for this research is a practical problem concerning the routing of buses chartered by UNICAMP for transporting a part of its employees, which is characterized as a rich model. The goal is to optimize this process by minimizing the total travel distance or the number of vehicles used, with a consequent reduction of the expenses incurred by the University. Therefore, in addition to its scientific aspect, this dissertation gives results with real chances to benefit the administration of a public university. For this to happen, the heuristics developed were entered into a geographic information system, which will be used by the university in the process of creation and optimization of routes to be publicly auctioned (AU)

• FAPESP's process: 07/06864-6 - Analysis of heuristic algorithms for rich vehicle routing problems
• Grantee: Peterson Katagiri Zilli
• Support Opportunities: Scholarships in Brazil - Master