2015

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Solving the quadratic shortest path problem
Description:	Borzou Rostami Finding the shortest path in a directed graph is one of the most important combinatorial optimization problems, having applications in a wide range of fields. In its basic version, however, the problem fails to represent situations in which the value of the objective function is determined not only by the choice of each single arc, but also by the combined presence of pairs of arcs in the solution. In this paper we model these situations as a Quadratic Shortest Path Problem, which calls for the minimization of a quadratic objective function subject to shortest-path constraints. We prove strong NP-hardness of the problem and analyze polynomially solvable special cases, obtained by restricting the distance of arc pairs in the graph that appear jointly in a quadratic monomial of the objective function. Based on this special case and problem structure, we devise fast lower bounding procedures for the general problem and show computationally that they clearly outperform other approaches proposed in the literature in terms of their strength.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	A branch-and-cut-and-price algorithm for the green vehicle routing problem with partial recharges and multiple technologies
Description:	Alberto Ceselli Abstract: We tackle a variation of the vehicle routing problem in which the transportation fleet is composed of electric vehicles with limited autonomy in need for recharge during the execution of their duties. Different technologies can be chosen at each station, offering different trade-off between recharge cost and time. We present an algorithm exploiting column generation, cutting planes and branch-and-bound for the exact solution of the problem. The pricing phase requires elementary resource constrained shortest path problems to be solved, and is carried out with both heuristics and an exact dynamic programming routine. The cut separation phase is performed by running heuristics from the literature on a particular support graph. Experiments on benchmark instances from the VRP literature reveal that our algorithm is effective in solving instances with up to thirty customers, nine recharge stations, five vehicles and three technologies to optimality.