Computational Modelling Group

• Login/Register

You are here:

• CMG Home
• Events
• CORMSIS Seminar: Metaheuistics for an Integrated Vehicle Routing and Container Loading Problem

Web page

http://www.cormsis.soton.ac.uk/seminars/default.php

Submitter

Deborah Guy

We consider the integrated problem of vehicle routing and container loading, involving practical constrains that are often found in freight transportation. This problem is an extension of the vehicle routing problem with time windows (VRPTW) and is called the vehicle routing problem with three-dimensional loading constraints (3L-VRPTW). It consists of a number of customers, each requiring a demand of items composed of rectangular boxes of given sizes and a total weight. A fleet having a maximum number of vehicles with the same three-dimensional loading space and the same weight capacity starting from a single depot must deliver the required items and then return to the depot. All items required by a customer must be placed on the same vehicle. The problem then involves the determination of vehicle routes such that, for each vehicle, boxes do not overlap, the weight capacity is not exceeded and the total travel distance is minimized. In addition to the above constraints, operational loading constraints such as orientation, stability and LIFO policy are taken into account. We propose a tabu search algorithm for the VRPTW in which the assignment of a customer to a vehicle is evaluated by a combined function that penalizes the excess of weight and the excess of the loading space length. For the loading problem, we suggest a multi-start random constructive heuristic with a load arrangement based on cuboids that fit in given empty spaces. Computational results on instances from the literature are presented.

Tea/coffee will be available before the start of the seminar.