Nested Partitions Method for the Local Pickup and Delivery Problem

We consider a problem in which a set of loads are to be moved by vehicles in a local service area in an optimal manner so as to maximize the overall profit over a given planning horizon. The problem is a general transportation problem with nonhomogeneous resources, and mixed integer linear programming (MILP) formulations are adopted, which can then be solved using off-the-shelf MILP solvers. Furthermore, we embark on a new approach based on a specialization of the nested partitions (NP) method - a meta-heuristic for combinatorial optimization problems. We also propose a number of NP-oriented techniques: (i) linear programming (LP) solution-based biased sampling, which turns to LP solution information for guidance toward good solutions, (ii) sampling-based (or LP solution-based) partitioning that uses sampling results (or the LP solution information) for purposes of deriving effective partitioning schemes, flexible backtracking, etc. These techniques, when used in conjunction with NP, can substantially enhance its efficacy. Our computational results show that on problems of realistic scale, our adapted NP approach overwhelmingly outperforms the standard approach of applying a commercial solver (ILOG CPLEX 9.1 in our experiments) to MILP formulations in terms of both computation time and solution quality