Çok modlu tarifeli seferlere sahip taşıma şebekesinde çok ürünlü rotalama problemi

We study a multicommodity network flow problem faced by a third party logisticscompany that has the possibility of using ground and maritime transportation.We are given a set of commodities which should be picked up from their originsat given release times and should be delivered to their destinations no later thantheir duedates. The commodities may be carried directly from their origins totheir destinations on trucks, or they may be carried on trucks to a seaport, mayvisit several seaports using maritime services, and then to be carried to their destinationson trucks. There is no capacity and time limitation on the use of groundtransportation. However, the maritime services are scheduled in advance and thecompany has limitations on the amounts of volume that it can use on each service.The aim is to determine routes for commodities in order to minimize the sum oftransportation cost and stocking costs at seaports, respecting the capacity andtime related constraints. We call this problem the ?Multimodal MulticommodityRouting Problem with Scheduled Services (MMR-S)?. We first prove that theproblem is NP-hard. Next, we propose a first mixed integer programming formulationand strengthen it using variable fixing and valid inequalities.We relax thecapacity constraints in a Lagrangian manner and show that the relaxed problemsdecompose into a series of shortest path problems defined on networks augmentedby time for each commodity. The corresponding Lagrangian dual yields a lowerbound, which may be stronger than that of the linear programming relaxationof our first formulation. Then, we provide an extended formulation whose linearprogramming relaxation gives the same bound as the Lagrangian dual. Finally,we use the Lagrangian relaxation to devise heuristic methods and report theresults of our computational study.