Provided an LDD instance for which at least one feasible delivery plan can be scheduled for it without adding extra flights. The optimization problem aims at finding such a solution that the completion time of all the delivery tasks is minimized.
As each flight must be expressed by varibles, the problem can be formulated with an mixed integer linear program (MILP) based on a network constructed with bi-types of arcs. The problem, which is evidently NP-complete generalizing the routing problem, is very difficult to solve.
Our computational tests show that the aggregation will result in 26% integer variables reduction, 19% continuous variables reduction and 8% constraints reduction averagely. And 34 new instances are solved to optimal using strengthened formulation compared 26 using the original MILP.The tests also show that the parallel and nonparallel NSHs find 57.3% best solutions (8.8% optimal) for all the 172 instances compared with the results solved by the well-known solver GUROBI on the strengthened MILP
All the instances as well as the detail solutions are available on the website. And a simple statistical results can also be found in the right-hand of the first page.
For further information please don't hesitate to contact us.