Optimal Management of Logistic Activities in Multi-Site Environments

DONDO, RODOLFO; MENDEZ, CARLOS; CERDÁ, JAIME

COMPUTERS AND CHEMICAL ENGINEERING

Elsevier

Año: 2007

0098-1354

Abstract: The new emerging area of Enterprise Wide Optimization (EWO) has focused the attention in effectively solving the combined production/distribution scheduling problem. The importance of logistic activities performed in multi-site environments comes from the relative magnitude of the associated pickup and delivery costs and the good chance of getting large savings on such expenses. This paper first develops a rigorous MILP mathematical formulation for the multiple vehicle time window-constrained pickup and delivery (MVPDPTW) problem. The approach is able to account for many-to-many transportation requests, pure pickup and delivery tasks, heterogeneous vehicles and multiple depots. Optimal solutions for a variety of benchmark problems with cluster/random distributions of pickup & delivery locations and limited sizes in terms of customer requests and vehicles have been discovered. However, the computational cost exponentially grows with the number of requests. For large-scale m-PDPTW problems, a local search improvement algorithm to steadily get a better solution through two evolutionary steps is also presented. In the first step, the neighborhood structure around the starting solution is generated by implicitly performing multiple, non-balanced request exchanges among nearby trips, and fully explored to find the best neighbor (the improvement step). In the second stage, a new neighborhood developed by reordering nodes on every individual route is considered (the intensification step). If a better set of routes is found, both steps are repeated until no improved solution is discovered. A well-defined neighborhood structure on each step permits to identify not only the feasible moves (the problem variables) but also the solution space (the problem constraints) to be explored. In this way, manageable MILP mathematical formulations for both subproblems have been developed and solved through an efficient branch-and-bound algorithm. To decrease the likelihood of getting stuck in a poor local optimal, a mixed-mode is activated whenever the normal mode fails to find a better neighbor. A significant number of large-scale m-PDPTW benchmark problems, some of them including up to 100 transportation requests, multiple depots and different vehicle-types, were successfully solved within acceptable CPU times.