Title: Solution approaches for determining user-oriented paths on dynamic networks

Authors: Luigi Di Puglia Pugliese; Francesca Guerriero

Addresses: Department of Mechanical, Energy and Management Engineering, University of Calabria, Via Pietro Bucci, 87036 Arcavacada di Rende Cosenza, Italy ' Department of Mechanical, Energy and Management Engineering, University of Calabria, Via Pietro Bucci, 87036 Arcavacada di Rende Cosenza, Italy

Abstract: This paper addresses the time dependent multi-objective constrained shortest path problem. Solving the problem aims at providing the user a Pareto-optimal solution associated with an efficient path. The solution process takes into account information given by the user in order to obtain a path, satisfying his/her requirements. For the first time, more than two criteria are considered and the reference point methodology is used to define the aggregation function. In addition, knapsack-like constraints are introduced in the formulation in order to model budget restrictions. Dynamic-programming-based algorithms are devised and tested on randomly generated networks and on real life instances derived from US city maps. The computational results underline that the proposed algorithms are able to solve the problem in a reasonable amount of time. This is a good result since the problem considered contains features of three NP-hard problems: the multi-objective, the constrained and the time dependent shortest path problems.

Keywords: dynamic programming; user-oriented paths; dynamic networks; routing problem; time dependent parameters; shortest path; multiobjective optimisation; quality of service; QoS; Pareto-optimal solutions; reference point; modelling; budget restrictions.

DOI: 10.1504/IJSCIM.2015.071932

International Journal of Supply Chain and Inventory Management, 2015 Vol.1 No.1, pp.6 - 30

Received: 27 Feb 2014
Accepted: 24 Sep 2014

Published online: 24 Sep 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article