A Multi-objective Ant Colony System Method for a Robust Selective Full Truckload Vehicle Routing Problem

The truck backhauling problem has attracted the interest of many global road transportation companies. The problem is reducing empty truck miles by having truckers carry orders along their route back to their origins. The return orders can vary in terms of their origins and destinations, their profits and their pickup and delivery time windows. Moreover, the travel time from one location to another location can be uncertain and change depending on a number of expected scenarios. This work addresses a robust full truckload commodity selection and multiple depot vehicle routing problem with time windows (RFTSMDVRPTW) under travel time uncertainty. The robustness consists of designing a set of feasible selective routes in all scenarios that maximize overall profit and minimize the worst observation of the total travel time across all scenarios subject to time window constraints. We introduce a multi-objective ant colony system algorithm for solving the RFTSMDVRPTW. We demonstrate the effectiveness and efficiency of the proposed approach through numerical experiments on randomly generated instances for the problem under consideration.