Master Thesis Defense by Martin Damyanov Aleksandrov
Mr Martin Damyanov Aleksandrov defended his master thesis on 'Heuristics and Policies for Online Pickup and Delivery Problems'
Mr Martin Damyanov Aleksandrov defended his master thesis on 'Heuristics and Policies for Online Pickup and Delivery Problems' at UNL on 15 October 2012
Abstract:
In the last few decades more and more research attention has been dedicated to a specific subclass of Vehicle Routing Problems due to its significant importance in several transportation areas such as taxi companies, courier companies, transportation of people, organ transportation, etc. These problems are characterized with their dynamicity as the demands are, in general, unknown in advance and the locations related with them are paired. Therefore, in this thesis we focus exactly on a version of Dynamic Pickup and Delivery Problems with a particular attention to the process of learning simple dispatch heuristics in an optimal way. We were motivated by a problem arised in an Australian courier company, which operates in Sydney, Melbourne and Brisbane, where almost every day more than a thousand transportation orders arrive and need to be accommodated. The fi rm has a fleet of almost two hundred various types of vehicles, which operates mostly within the city areas and which are assigned to particular regions of these areas. Thus, whenever new orders arrive at the system the dispatchers are in front of a complex decision epoch related with the allocation of the new customers within an already existing route and at the same time achieving a complex multi-level objective function as much as possible. In this thesis we present a recommendation system able to rank simple dispatch heuristics. We implemented eight of these, observing different characteristics of the current fleet and orders. It incorporates an artificial neural network that is educated on the basis of two hundred days of past data. The training process was conducted under the supervision of schedules produced by Indigo, i.e. an oracle able to produce suboptimal solutions when given problem instances. The system leaves open a possibility for many dispatch policies to be implemented that are based on this rule ranking. It also allows for constructing fleet schedules helping dispatchers in the company to manage the vehicles. In addition, we obtained results a hiring plan for the human resources each single day and within the di fferent periods of the day. The results obtained are very interesting and promising. The latter give basis for several prize-winning future prospects such as channel fleet management, considering traffic conditions, constructing crew schedules for loading and unloading heavy packages and learning hyper-heuristics able to control simple-rule sequences.