Scientific Program > Talks by Speaker > Sarbinowski Antoine

Given a set of stations where vehicles can be parked, associated with excess or deficit values, we search the routing and loading instructions of a set of carriers that will correct these excesses and deficits. We address the static case and we do not consider transshipments, which corresponds to the non-preemptive case. The tours should respect carriers capacity and timespan constraints, and minimize a multicriterion value composed of the number of carriers, the sum of carriers tours durations and the carried vehicles indisponibility time. Lower bounds can be computed either by solving a min-cost assignment problem, which determines how many vehicles are to be moved from a station to another, or by solving a min-cost flow problem. We propose two heuristic approaches to compute feasible solutions. One consists in solving the min-cost assignment resulting in a set of Pickup and Delivery requests, then solving the related PDP. The approximation ratio for this strategy, when focusing on minimizing the carriers riding time, increases with the capacity of the carriers. Thus, the two subproblems are combined in a local search scheme allowing to improve the solution. The other heuristic consists in solving a min-cost flow problem from which the carriers tours are derived, and computing loading instructions on these tours thanks to another flow model. The heuristics were launched on random instances. Results were compared to the lower bounds and the obtained gap ranges from 1% to 30%, depending on the instance size and the heuristic being used.