My research interests are in the area of combinatorial optimization. Specifically, transportation problems such as the Vehicle Routing Problem and Arc Routing problem.
The transportation of goods and people continues to be a vital function in the world we live in today. The Energy Information Administration (EIA) predicts that over the next 25 years, world demand for liquid fuels and other petroleum is expected to increase more rapidly in the transportation sector than in any other end-use sector. A portion of this increase comes about quite naturally through the economic expansion of poorer countries, however, a large proportion comes from the increasing demands of society as a whole.
Enormous sums of money are spent each year by businesses on logistics, namely on petrol, repairs and associated workforce costs. In addition to these measurable costs, there are other ethical issues that play more and more of a role today, most notably that of carbon emissions. Given the growing evidence of climate change, the effect of overusing transportation systems is potentially catastrophic. Through effective planning and the improvement of algorithmic techniques, the burden on our world can be helped.
The multitude of research already undertaken into such transportation problems, is largely due to their real world applicability. Numerous techniques proposed have been used in real world scenarios and many have proved successful in reducing associated transport and emission costs. However, there remains wide scope for new techniques.
The practical applicability of routing and scheduling algorithms is varied and diverse. Consider a typical courier company, where each day the delivery of goods to a number of customers need to be scheduled. Making these deliveries on an ad hoc basis with no forethought will ultimately result in inefficiencies. Drivers will typically be covering excessive distances, resulting in higher wage, fuel and maintenance costs. However, by planning deliveries, these associated costs can be reduced.
The field of optimization involves applying a set of planning techniques so as to minimise these associated costs. Exactly which costs should be minimised is specific to each problem, e.g. in the case of the courier, the requirement might be to minimise the overall travelling distance of the vehicle fleet. Alternatively, in addition to minimising overall travelling distance, there could also be a requirement that for any given route the driving time to complete that should not exceed 3 hours. For any given problem, there may exist one or more such constraints.
A widely known optimization problem, called the Vehicle Routing Problem (VRP), has been well studied within the scientific community, since its first conception in 1954. The VRP involves finding a set of routes for a fleet of vehicles (each departing from/returning to the same depot), to service a set of customers, such that each customer is served by exactly one vehicle. The objective is to minimise the cost of making the customer deliveries.
A number of extensions to this basic problem to deal with further constraints exist, such as the Capacitated Vehicle Routing Problem (CVRP). Here, a capacity constraint is placed on each vehicle and assumptions are made that a fleet of vehicles are available, all of which are capable of holding an identical fixed capacity. The quantity demanded by each customer must be less than the capacity of a single vehicle and known in advance. The objective is to minimise the cost of making the customer deliveries.