Skip to main content

Meta-Heuristics for the Multiple Trip Vehicle Routing Problem with Backhauls

Wassan, Naveed Ahmed Meta-Heuristics for the Multiple Trip Vehicle Routing Problem with Backhauls. Doctor of Philosophy (PhD) thesis, University of Kent,. (KAR id:56731)

Language: English
Download (1MB) Preview
[thumbnail of 201PhD Thesis_NaveedWassan_FinalVersion.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format


With the growing and more accessible computational power, the demand for robust and sophisticated computerised optimisation is increasing for logistical problems. By making good use of computational technologies, the research in this thesis concentrates on efficient fleet management by studying a class of vehicle routing problems and developing efficient solution algorithms.

On the solution methodologies development side, the proposed research noted some considerable and impressive developments. Although, it is well established that the VRPs belong to the NP-hard combinatorial class of problems, there are considerable efforts on the development of exact methods. However the literature is full of a variety of heuristic methodologies including the classical and the most modern hybrid approaches. Among the hybrid approaches, the most recent one noted is mat-heuristics that combine heuristics and mathematical programming techniques to solve combinatorial optimisation problems. The mat-heuristics approaches appear to be comparatively in its infant age at this point in time. However this is an exciting area of research which seeks more attention in the literature. Hence, a good part of this research is devoted to the development of a hybrid approach that combines heuristics and mathematical programming techniques.

The CPLEX implementation produced optimal solutions for a good number of small and medium size data instances of the MT-VRPB and generated lower bounds for all instances. The CPLEX success may be considered as modest, but the produced results proved very important for the validation of the heuristic results produced in the thesis.

To investigate this new variant further, we developed an algorithm belonging to the new class of the hybrid methodologies, i.e., mat-heuristics. A hybrid collaborative sequential mat-heuristic approach called the CSMH to solve the MT-VRPB is developed. The exact method approach produced in Chapter 4 is then hybridised with the Two-Level VNS algorithm developed in Chapter 5. The overall performance of the CSMH remained very encouraging in terms of the solution quality and the time taken on average compared with the CPLEX and the Two-Level VNS meta-heuristic.

The results in this research show that significant cost savings could be obtained by choosing the right fleet size and better vehicle utilisations with multiple trips and backhauling. Hence, the research proved the justification of studying this interesting combination. Moreover, the problem modelling, efficient algorithm design and implementation, and the research results reveal some vital information and implications from the managerial point of view in terms of making the tactical (fleet acquisition) and the operational (fleet management) decisions in a more informative manner.

Item Type: Thesis (Doctor of Philosophy (PhD))
Thesis advisor: Nagy, Dr. Gabor
Thesis advisor: Salhi, Prof. Said
Uncontrolled keywords: Vehicle Routing Problems Multiple Trips Backhauling Heuristics Meta-heuristics Mat-heuristics Combinatorial Optimisation Distribution Logistics
Subjects: H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management
Divisions: Divisions > Kent Business School > Kent Business School
Divisions > Kent Business School > Centre for Logistics and Heuristic Optimisation
Depositing User: Users 1 not found.
Date Deposited: 03 Aug 2016 17:00 UTC
Last Modified: 16 Feb 2021 13:36 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year