Distributed Algorithms and Software for Vehicle Routing Optimization in Small and Medium Enterprises

Enterprises in the road transportation sector have to face several difficult challenges. Namely, they have to design distribution strategies and policies which combine economic efficiency with sustainability criteria. This issue is critical, especially for small and medium enterprises (SME), since they hardly have the economic and human resources necessary to implement and manage the complex mathematical methods associated with routing optimization -i.e. metaheuristics, mathematical programming methods, and so on. Similarly, current computing technologies -such as commercial software licenses or cluster infrastructures-, are not always affordable to most of these companies. However, it is obvious that these methods and technologies could help them to significantly improve their productivity levels by reducing costs and by making their business model more competitive and sustainable. Thus, the ultimate mission of this project proposal is to offer efficient solutions to the aforementioned challenges. To this end, we propose the development of methodologies, optimization algorithms and open source software -and therefore software affordable to most SMEs- which can be used by companies in the transportation sector to develop efficient, sustainable and environment-friendly delivering strategies. These solutions are expected to be particularly useful in realistic scenarios characterised by different levels of uncertainty -e.g. customers with stochastic demands, random behaviors associated with transportation and service times, etc. The introduction of environmental criteria in the decision making process implies the consideration of traditional costs (i.e. petrol consumption or workers’ salaries, for instance) along with other costs related to environmental factors (e.g. acoustic and air pollution) according to the legal regulations that are in force in Europe and Spain. The authors of this proposal consider that this mission, even being ambitious, can be achieved by the research teams supporting the proposal. These teams constitute an interdisciplinary group with long experience in similar shared projects. The following arguments reinforce the idea that this mission can be accomplished by the members of this group:

  • They accumulate a long expertise on the Vehicle Routing Problem, its newest and most advanced variants and the best known algorithms and methods (both complete and incomplete). In fact, some of these methods have been developed by researchers of this group and published in international journals, books and conferences.
  • They are aware of suitable techniques and procedures to perform the environmental costs measurement in the road transportation. Some of these techniques have been developed by researchers of these teams in previous research projects funded by the Spanish Ministry of Innovation and other national and international institutions.
  • They hold the know-how associated with the development of the distributed software which allows sharing computing resources among different machines.
  • Some of the members of the research group show experience in the use of mobile communication systems and geographic information systems (GIS), which can be necessary to perform monitoring processes of the transportation tasks, along with "real-time" routing re-design whenever unexpected events take place -e.g. heavy traffic, demand variations, accidents, and so on.
  • They are in touch with several companies in the transportation sector and consultancies which have shown interest in actively contributing to the project development and, thus, benefit from their methodological and technological outputs.

 Therefore, each research team has an assigned target to fulfil, being the global mission of this project the result of the coordination of the following sub-missions: (a) the team from the Public University of Navarre (UPNA team), which includes researchers from the fields of Operations Research and Economics, will focus on the development of economic models to internalise environmental factors in the cost functions to be minimised; (b) the team from the Open University of Catalonia (UOC team), which includes researchers from the fields of Computer Engineering, Mathematics, and Management, will work in the adaptation of routing heuristic algorithms to solve realistic delivery problems; and (c) the team from the Autonomous University of Barcelona (UAB team), which includes researchers from the fields of System Engineering and Automatics, will develop the software and the mathematical models to solve the routing problems in an exact way -in those cases where this approach is suitable. According to the previous paragraph, the following main general objectives can be established:

  1. Diagnosis and statement of the main concerns, current needs and future challenges of road transportation, focusing on its economic and environmental impact.
  2. To develop modeling methodologies that allow for formal representation of different distribution and routing problems and to implement models able to represent realistic transportation scenarios.
  3. To develop and to implement flexible, efficient and robust algorithms in order to provide optimal or quasi-optimal solutions to realistic distribution and routing problems.
  4. To reduce the entry barrier to optimization technology by designing a computational infrastructure that enables enterprises to improve their distribution strategies and routing operation by using affordable software and hardware resources.  

 Finally, it is important to highlight that the teams that support this proposal are co-founders of the HAROSA Knowledge Community (http://dpcs.uoc.edu/joomla/index.php/about-harosa-kc). The HAROSA KC is a scientific international and interdisciplinary community composed by 10 research groups from Spain and 6 research groups from the rest of the world. The HAROSA mission is the development of "Hybrid Algorithms for solving Realistic rOuting, Scheduling and Availability problems". Being relevant members of the HAROSA Knowledge Community guarantees the international visibility of the proposal along with its viability, since it can be also supported with HAROSA funds already obtained in different competitive calls. Moreover, the research group owns a powerful computer cluster and some workstations equipped with state-of-the-art graphical process unit processors (GPUs), which have been provided by NVIDIA Inc. to support our research. Finally, it should be also noticed that the UOC team is member of the organization PanetLab (http://www.planet-lab.org/), and thus they can use its resources during the development and tests phases of the distributed system to be constructed.

Saturday, January 1, 2011 (All day) - Tuesday, January 1, 2013 (All day)

Pau Fonseca i Casas
Department of Statistics and Operations Research

Universitat Politècnica de Catalunya - BarcelonaTECH
North Campus - C5218 Room
Barcelona, 08034, SPAIN

Tel. (+34) 93 4017035
Fax. (+34) 93 4015855