< Back to previous page

Project

Maximizing User Benefits by Changes in Incomplete Networks.

Maximizing User Benefits by Changes in Incomplete Networks
Every day the available vehicles of a transport company are scheduled to deliver or pick up large amounts of packages at the customers. Since not all customers order every day, only a selection of the known customers should be visited during a day. This leads to complex scheduling problems for the changing group of selected customers, since the location of the customers are widely spread throughout a road network. Also a depot is located somewhere is this network, from where the scheduled routes for the vehicles should start and end. It is reasonable to assume that in a road network there is not always a direct path available between each pairof locations, which means that the network is incomplete. Since the group of customers which should be visited, will vary from day to day, the scheduled routes for the vehicles and therefore the used roads of the network will also vary. From an economic point of view the transport company will minimize its transportations costs. Since the company should paythe drivers for the time they are en route, the total travel time of scheduled routes for the vehicles should be minimized, while all availablevehicles have a restricted capacity. This daily scheduling problem can be transformed into a Vehicle Routing Problem (VRP), which is widely studied in literature. 
In this research we will investigate the possibility that the transport company has to improve the network. This improvement can be the construction of a new road between two locations which have yet no direct connection. Another possibility is to widen a road between two locations, whether or not in combination with the transposition of that road into a one-way-street. As a result of one of these changes in the road network the distance and consequently the travel time between these two locations will be decreased. This reduced travel time could also decrease the travel time between other pairs of locations where the shortest connection will contain this new or widened road. When the widened road is converted into a one-way-street, this has negative effects on the travel time for the traffic in the opposite way. Consequently, shortest connections between other pairs of locations could be negatively involved, since this connection is no longer available. 
The main goal is to find the best improvement in the existing road network. The most intuitive way to find this best improvement is to execute the daily scheduling problem for each network where one of the possible changes is implemented. The improvement which is made in the network wherethe average daily total travel time is the lowest is simply the best improvement. Unfortunately, when the number of customers goes up, the number of possible changes is growing exponentially. This means that when the number of known customers is very large, the time to find the best improvement in the road network is extremely large and for practical applications it is not an option to investigate all possibilities. Therefore, we will develop an efficient (meta-)heuristic in order to look for the best network improvement. 

Date:1 Sep 2013 →  31 Dec 2018
Keywords:Vehicle Routing Problem
Disciplines:Business administration and accounting, Management
Project type:PhD project