Pisa - Dipartimento di Informatica - Research Evaluation Exercise 1999


Transportation and Logistics:
Models and Algorithms



Proposer: Giorgio Gallo



The research project contains several different modules, each characterized by the application area and the type of methodology involved. The following table illustrates the relations among the different application and methodology sectors.


\begin{tabular}{\vert c\vert c\vert c\vert c\vert}
\hline
& Transportation: & ...
...$\ & & \\
\hline
Heuristics & $\surd$\ & & $\surd$\ \\
\hline
\end{tabular}% WIDTH=663 HEIGHT=142


Although to fully understand the motivation and rationale of the different researches one has to start from the application areas, in the following, for the sake of the clarity and of the conciseness, we shall use the methodologies as a guidance criterion for the group's activity presentation.

State of the Art and Trends:


Networks and Flows


Network models and algorithms have played a fundamental role in the development of Operations Research and Management Science since the initial times of these disciplines. Network optimization lies in the middle of the great divide which separates the two major types of optimization problems, continuous and discrete, and has benefitted from the advancements in both areas, while, at the same time, it has largely contributed to such advances.
Network problems such as shortest paths, assignment, max-flow, transportation, transhipment, spanning trees, matching, traveling salesman, generalized assignment, vehicle routing and multicommodity flows constitute the most common classes of practical optimization problems in the area. In spite of the large body of research done in the past, there is still a huge amount of research going on in the quest of always faster algorithms capable of tackling the growing size and the complexity of real life applications. This fact is proved by the large number of articles on network optimization which appear every month in leading scientific journals such as Mathematical Programming, Networks, Informs Journal on Computing and Operations Research. To get an idea of the state of the art in this sector one can refer to some recent books and special journal issues such as [2], [36] and [18].

Directed Hypergraphs


Many problems can be found in different application areas, which, although featuring an underlying graph structure, cannot be represented as graph problems without losing some of their peculiar characteristics. This fact has led recently to the introduction of a generalization of graphs, the directed hypergraphs, which include as particular cases other well known generalizations such as labelled graphs and And-Or graphs. Directed hypergraphs are a powerful tool not only in modelling but also in solving several relevant problems in areas such as linear production problems, flexible manufacturing systems, propositional logic, relational databases, and public transportation systems [42,21,26].

Nondifferentiable Optimization


Minimizing a convex function which does not possess continuous derivatives is a rather difficult task which is required in many applications.
One traditional approach is the subgradient method. Of quite simple implementation, it suffers from a number of important drawbacks, among which the inability of providing a primal optimal solution together with the dual optimal solution, and its slow convergence rate.
The other fundamental class of algorithms for nondifferentiable optimization stems from the cutting plane method, and it is based on the idea of constructing a model of the function, to be progressively refined as the algorithm proceeds, which at each step is used to determine the new point(s) in which to evaluate the function. More efficient than the standard subgradient method, this approach is at present widely investigated. Examples of algorithms of this type can be found in [40].

Heuristics


Combinatorial optimization is concerned with optimal decisions in the case of discrete alternatives. In the last two decades, an enormous effort has been made to model real-life problems and to solve them through Combinatorial Optimization.
Almost all the practically relevant combinatorial optimization problems belong to the class of the difficult (NP-hard) problems, which, in addition to the large size of real life applications, makes their exact solution usually rather unpractical. That explains the huge number of papers and books dealing with ``heuristic'' techniques.
Local search is the main algorithmic paradigm underlying the heuristic approaches to solve combinatorial optimization problems. In a local search method one moves from the current solution to a neighboring one, trying to improve the objective function, until a ``good'' local optimal solution is found.
Lying in the interface between mathematics, computer science and operations research, the research on local search has originated a large body of literature. Methods such as ``Simulated annealing'', ``Tabu search'', ``Genetic algorithms'', which belong to this class, are currently used to solve optimization problems arising in a large variety of applications [41,39,38,35,37].

Relevant Research Activities at the Department


Networks and Flows


Shortest paths.

A traditional research subject for the group [22], the activity in this area, in the last years, has focused on ``auction'' and ``dual-ascent'' methods. A new auction algorithm running in strongly polynomial time has been introduced, whose practical efficiency has been extensively tested; parallel implementations are currently being studied [1]. A new family of dual-ascent methods, called Hanging algorithms, has been proposed [32]. More recently, the interest has been drawn on dynamic networks, i.e. networks where the distances are functions of the time; the search of shortest paths on these networks is particularly relevant in transportation planning [33].

Optimal flows.

Efficient serial and parallel algorithms to solve large scale minimum cost multicommodity flow problems have been studied and have served as a test bed for the developement of general codes for nondifferentiable optimization [15,4]. This research has been motivated by a certain number of relevant application: transportation and routing problems [11], timetabling in freight transportation, crew scheduling [] and network design [9,10] problems.
Other particular flow problems have been studied, among them the balanced flow problem, i.e. a problem where an ``equitable distribution'' of the flow is wanted [34].

Directed hypergraphs and hyperflows


The research developed in this area has been aimed both to the sistematic analysis of the hypergraph theoretic properties and to particular classes of hypergraph optimization problems [21,26].
A Simplex-like algorithm for the capacitated minimum cost hyperflow problem, based on the characterization of the basis structures in terms of spanning hypertrees, has been proposed and widely tested [3,20].
The analysis of the demand in transit systems has been one of the first applications to motivate the research on directed hypergraphs: in fact, the passengers' behaviour in a transit network can be better modelled making use of hyperpaths in directed hypergraphs rather than using paths in standard graphs. Furthermore, the use of directed hypergraph to model the transit network has proven crucial in extending to the public transportation setting the equilibrium models developed for the analysis of private transportation [29,30].
Another important application, which actually has contributed to originate the research on directed hypergraphs, is the ``satisfiability problem''. A satisfiability problem can be formulated as the problem of finding a hyperpath between two nodes in a directed hypergraph [5,24], while the problem of finding the minimum number of clauses to be deleted in order to make a formula satisfiable can be formulated as the problem of finding a minimum cutset in a directed hypergraph [17].
Other interesting applications on which some research has been done is that of production systems. Namely both the cutting stock problem [27] and the problem of finding, in a manufacturing system, an assemblying plan which allow the production of a given item at minimum `cost' [25], can be formulated and solved by means of hypergraph techniques.

Nondifferentiable Optimization


Motivated by some applications involving multicommodity flow problems, the research work in this area has started with the implementation of a generic code for (constrained) nondifferential optimization, based on the ``traditional'' penalty Bundle approach [12]. This solver has already been successfully used in different applications, among which we mention: sequential [15] and parallel [4] cost-decomposition approaches for multicommodity flow problems, computation of lower bounds for the capacitated fixed-charge multicommodity flow problem [9,10], Lagrangean heuristic approaches to crew scheduling problems [7] and computation of lower bounds for the capacitated minimum spanning tree problem [16].
A methodological contribution of this research has been the introduction of a class of generalized Bundle methods that subsumes several known Bundle variants [14].

Heuristics


A relevant research sector is the one concerned with the heuristic solution of hard combinatorial optimization and decision problems. In particular, expertise and skills in obtaining both theoretical and algorithmic results, and solving real life applications, have been developed by the group in the following areas: crew scheduling problems [5]; vehicle scheduling and transportation problems [8,31,28]; logistics and distribution problems [11]; scheduling and sequencing of activities on machines [23]; cutting stock and assembly problems [27,25].
In most of the above mentioned problems the outline of the approach followed can be described as follows: 1) analyse the problem structure and find a good formulation; 2) relax the problem or decompose it in easier subproblem; 3) solve the relaxation (nondifferentiable optimization methods find application here); 4) use the solution of the relaxation as a starting point for some heuristic algorithm (local search methods are typical tools in this phase).

Short Term Plans and Expected Results


Networks and Flows


Shortest paths.
The research on shortest paths shall continue, focusing on special classes of problems, motivated by applications in the area of transportation management: constrained shortest paths and shortest paths with time windows.
Constrained shortest paths arise in the column generation approach to crew scheduling problems. We have just started the re-engineering of a package for crew scheduling, based on relaxation and column generation, which is currently used in several Italian public transportation companies, and which has been originated with past research activity of the group. The goal is to improve its effectiveness, making it able to get better solutions at a lower computational cost. To obtain these results, the research will be focused on the column generation procedure and henceforth on the design of fast constrained shortest path algorithms. Being the constrained problems we are dealing with of the NP-hard type, heuristic algorithms will be studied.
Shortest paths with time windows play a fundamental role in algorithms for ``weak demand'' transportation systems, such as ``dial-a-ride'' systems. Again, this is a difficult problem, and heuristic techniques will be used for its solution.
Generalized assignment.
A research which is now being carried on concerns the management of the vehicle depots in a medium size Italian public transportation company. A mathematical programming model has been formulated which contains as a subproblem a ``generalized assignment'' problem. Algorithms for this problem shall be developed.
Path covering.
The rostering problem, that is the problem of assigning a given set of duties to the personnel within a given planning horizon, can be formulated as path covering problem on a multilayered graph. This is a typical problem which appears to be well suitable for the``multiexchange'' heuristic algorithms described in the next ``Heuristics'' section, and will be studied in that context.

Directed Hypergraphs


We plan to analyze the use of hypergraph models and algorithms for special classes of minimum makespan assemblying problems. That implies the implementation of the heuristic algorithm mentioned in the previous section and its use on test problems with different types of structure.

Nondifferentiable Optimization


We plan to enhance our Bundle code using the ideas developed in [14]. In particular, we will experiment with different alternatives to the standard quadratic stabilizing term, namely with those resulting in linear programming subproblems. We expect considerable performance's improvements, that should make it possible to approach very-large-scale nondifferentiable optimization problems. We plan to use the enhanced Bundle code to improve upon the results previously obtained, and to develop new Lagrangean-based approaches for several new problems.

Heuristics

In many different classes of combinatorial optimization problems arising in practical applications, a feasible solution can be characterized as a partition of a set of objects into a set of subsets, such that for each subset a certain class of properties hold. In many cases, the optimal solution is such that the structural relations among the elements within a single subset result from a nested optimisation problem.
Among the application areas for which this structure holds, we mention: 1) scheduling problems on parallel machines; 2) service center location and dimensioning; 3) delivery problems; 4) routing problems; 5) transportation problems; 6) vehicle and crew scheduling problems.
For this class of problems, the quality of a solution varies depending on the specific partition as well as on the possibility of efficiently optimising within the single subset belonging to the partition.
The aim of the research is to investigate and develop ``multiexchange'' local search methods which exploit the particular structure of the solutions mentioned above. The main idea is to map the set of feasible exchanges of a given partition on a graph, the ``exchange graph'' hereafter. The nodes of the exchange graph represent the subsets of the partition while the arcs model possible exchanges of elements within pairs of subsets, with the arc cost being an estimate of the variation of the objective function due to that particular exchange. Then, to find a better neighboring solution we look for a cycle or path of minimum cost (possibly negative cost) on the exchange graph. In view of that, in the short term, we shall focus on the development of efficient algorithms for the detection of negative paths and cycles on graph will be an useful instrument.

Long Term Scenarios


Networks and Flows


Different optimization problems on dynamic networks will be studied. This research is motivated by the activity on transportation planning.
The design of fast minimum cost multicommodity flow algorithms will mantain its interest and relevance in the future, mainly in view of applications to the design and analysis of mass transportation networks.

Directed Hypergraphs


A global approach to find an assemblying plan which minimizes some given criterion will be investigated. It shall be based on hypergraph models and on decomposition techniques; from the algorithmic point of view it will rely on the know-how that the group has gained in the research on nondifferential optimization.

Nondifferentiable Optimization


We envisage the development of Bundle method variants that are still not subsumed by our current theoretical framework, as well as the extension of our approach to more general problems such as variational inequality problems.

Heuristics


The long term goals are to develop an algorithmic paradigm based on the ``multiexchange'' approach, and to study its applicability to a large set of combinatorial problems of practical interest.
To do that, we intend first to analyse the classes of problems which share the structural property described above; in particular, we plan to investigate vehicle scheduling problems and scheduling problems on parallel machines. Then, the ``multiexchange'' algorithmic paradigm will be specialized to solve the studied problems.

Short CV's


Giorgio Gallo -

Born in Palermo, July 27, 1942. `Laurea' in Electronic Engineering, University of Palermo, 1967. Current position: Professor of Operations Research. Teaching: Operations Research, Combinatorial Optimization, Networks, Simulation. Research interests: Network optimization, Combinatorial optimization, Transportation models, Satisfiability, Scheduling. Most relevant papers: [22], [19],[21], [3], [17].

Stefano Pallottino -

Born in Rome, September 26, 1945. `Laurea' in Mathematics, University of Rome, 1969. Current position: Professor of Operations Research. Teaching: Operations Research, Combinatorial Optimization, Networks. Research interests: Network optimization, Combinatorial optimization, Transportation models, Directed hypergraphs. Most relevant papers: [22], [29],[21], [32], [28].

Maria Grazia Scutellà -

Born in Sesto ed Uniti (CR), December 23, 1961. `Laurea' in Computer Science, University of Pisa, 1985. Ph.D. in Computer Science, University of Pisa, 1990. Current position: Associate Professor of Operations Research. Teaching: Operations Research, Combinatorial Optimization, Networks. Research interests: Networks and Flows, Directed hypergraphs and hyperflows, Heuristics. Most relevant papers: [1], [3], [32], [33], [34].

Antonio Frangioni -

Born in Portoferraio (LI), Italy, April 2, 1968. `Laurea' in Computer Science, University of Pisa, 1992. Ph.D. in Computer Science, University of Pisa, 1996. Current position: Research Associate. Teaching: Mathematical Programming, Combinatorial Optimization. Research interests: NonDifferentiable Optimization, Multicommodity Flows, Combinatorial Optimization. Most relevant papers: [13], [12],[15], [9], [10].

Fernanda Farinaccio -

Born in Oratino (CB), Italy, May 30, 1968. `Laurea' in Computer Science, University of Pisa, 1993. Ph.D. in Applied Mathematics, University of Florence, 1998. Current position: Post-doc. Research interests: Combinatorial Optimization. Multicriteria Decison-aid. Data Envelopment Analysis. Heuristics. Most relevant papers: [6].

Collaborators

Ravindra K. Ahuja, Theodor G. Crainic, Federico Malucelli, Maddalena Nonato, Sang Nguyen, Daniele Pretolani, Andres Weintraub.

keywords

Network optimization, Network flows, Dircted hypergraphs, NonDifferentiable optimization, Heuristics, Transportation models, Crew scheduling, Production systems

Bibliography

Relevant Research group publications



1
Bertsekas D.P., S. Pallottino and M.G. Scutellà, ``Polynomial Auction algorithms for shortest paths'', Computational Optimization and Applications 4(2), 99-125, 1995

2
Simeone B., P.Toth, G.Gallo, F.Maffioli and S.Pallottino editors, ``Fortran codes for network optimization'', Annals of Operations Research 13, 1988

3
Cambini R., G. Gallo and M.G. Scutellà, ``Flows on hypergraphs'', Mathematical Programming 78, 195-217, 1997

4
Cappanera P. and A. Frangioni, ``Symmetric and Asymmetric Parallelization of a Cost-Decomposition Algorithm for Multi-Commodity Flow Problems'', TR 36/96, Dip. di Informatica, Univ. di Pisa (submitted to INFORMS J.on Computing), 1996

5
Carraresi P., G. Gallo and G. Rago: ``A hypergraph model for constraint logic programming and applications to bus drivers' scheduling'' Annals on Mathematics and Artificial Intelligence 8, 247-270, 1993

6
Carraresi P., F. Farinaccio and F. Malucelli: ``Testing Optimality for Quadratic 0-1 Problems'', TR 11/95, Dip. di Informatica, Univ. di Pisa (to appear on Mathematical Programming), 1999

7
Carraresi P., A. Frangioni and M. Nonato ``Applying Bundle Methods to Optimization of Polyhedral Functions: An Applications-Oriented Development'' Ricerca Operativa 74, 5-49, 1996

8
Carraresi P., F. Malucelli and S. Pallottino ``Regional mass transit assignment with resource constraints'' Transportation Research B 30, 81-98, 1996

9
Crainic T.G., A. Frangioni and B. Gendron ``Bundle-based Relaxation Methods for Multicommodity Capacitated Fixed Charge Network Design Problems'' to appear on Discrete Applied Mathematics, 1999

10
Crainic T.G., A. Frangioni and B. Gendron ``Multicommodity Capacitated Network Design'' to appear in (B. Sanso and P. Soriano, eds.) Telecommunications Network Planning, Kluwer Academics Publishers, 1999

11
Equi L., G. Gallo, S. Marziale and A. Weintraub ``A combined transportation and scheduling problem'', European Journal of Operational Research 97, 94-104, 1997

12
Frangioni A. ``Solving Semidefinite Quadratic Problems Within Nonsmooth Optimization Algorithms'' Computers & O.R. 23, 1099-1118, 1996

13
Frangioni, A., ``On a New Class of Bilevel Programming Problems and its Use For Reformulating Mixed Integer Problems'', EJOR 82, p. 615 - 646, 1995

14
Frangioni A. ``Generalized Bundle Methods'' TR 04/98, Dip. di Informatica, Univ. di Pisa (submitted to SIAM J. on Optimization), 1998

15
Frangioni A. and G. Gallo ``A Bundle type Dual-ascent Approach to Linear Multicommodity Min Cost Flow Problems'' to appear in INFORMS JOC, 1999

16
Frangioni A., D. Pretolani and M.G. Scutellà ``Fast Lower Bounds for the Capacitated Minimum Spanning Tree Problem'' TR 05/99, Dip. di Informatica, Univ. di Pisa (submitted to Networks), 1999

17
Gallo G., C. Gentile, D. Pretolani and G. Rago ``Max Horn Sat and the Minimum Cut Problem on Directed Hypergraphs'' Mathematical Programming 80, 213-237, 1998

18
Gallo G. and M. D. Grigoriadis, eds. ``Netwok Optimization: Algorithms and Applications'' Mathematical Programming B 78, 1997

19
Gallo G., M.D. Grigoriadis and R.E. Tarjan, ``A fast parametric maximum flow algorithm'' SIAM Journal on Computing 9, 30-55, 1989

20
Gallo G., F. Licheri and M.G. Scutellà ``The Hypergraph Simplex Approach: some experimental results'' Ricerca Operativa 78, 21-54, 1996

21
Gallo G., G. Longo, S. Nguyen and S. Pallottino ``Directed hypergraphs and applications'' Discrete Applied Mathematics 42, 177-201, 1993

22
Gallo G. and S. Pallottino ``Shortest path methods: a unifying approach'' Mathematical Programming Study 26, 38-64, 1986

23
Gallo G. and F. Piccinonno ``A 1/4 approximate algorithm for P2/tree/Cmax'' Discrete Applied Mathematics 72, 85-98, 1997

24
Gallo G. and D. Pretolani ``A new algorithm for the propositional satisfiability problem'' Discrete Applied Mathematics 60, 159-179, 1995

25
Gallo,G. and M.G. Scutellà ``Minimum Makespan Assembly Problems'' TR 10/98, Dip. di Informatica, Univ. di Pisa, 1998

26
Gallo G. and M.G. Scutellà ``Directed Hypergraphs as a Modelling Paradigm'' to appear in Rivista AMASES, 1999

27
Gambale M., M. Nonato and M.G. Scutellà ``The Cutting Stock Problem: a new model based on hypergraph flows'' Ricerca Operativa 74, 73-97, 1995

28
Malucelli F., M. Nonato and S. Pallottino ``Demand Adaptive Systems: some proposals on flexible transit'' to appear in (T.A. Ciriani, S. Gliozzi, E.L. Johnson and R. Tadei, eds.), Operations Research in Industry, McMillan Press, London, 1999

29
Nguyen, S. and S. Pallottino, ``Equilibrium traffic assignment for large scale transit networks'', European Journal of Operational Research 37, 176-186, 1998

30
Nguyen S., S. Pallottino and M. Gendreau ``Implicit enumeration of hyperpaths in logit models for transit networks'', Transportation Science 32, 54-64, 1998

31
Nguyen S., S. Pallottino and F. Malucelli ``A modeling framework for the passenger assignment on a transport network with time-tables'' TR 13/98, Dip. di Informatica, Univ. di Pisa, 1998 (submitted to Transportation Science)

32
Pallottino S. and M.G. Scutellà ``Dual algorithms for the shortest path tree problem'' Networks 29, 125-133, 1997

33
Pallottino S. and M.G. Scutellà ``Shortest path algorithms in transportation models: classical and innovative aspects'' in (P. Marcotte and S. Nguyen, eds.) Equilibrium and Advanced Transportation Modelling, Kluwer, 245-281, 1998

34
Scutellà M.G. ``A strongly polynomial algorithm for the Uniform Balanced Network Flow Problem'' Discrete Applied Mathematics 81, 123-131, 1998

Other references



35
Aarts E. and J.K. Lenstra, eds. Local Search in Combinatorial Optimization, John Wiley & sons, Chichester, England, 1997

36
Ahuja R.K., T.L. Magnanti and J.B. Orlin Network Flows: Theory, Algorithms and Applications, Prentice-Hall, Englewood Cliffs, NJ 1993

37
Dell'Amico M., S. Martello and F. Maffioli, eds. Annotated Bibliographies in Combinatorial Optimization, Wiley, 1997

38
Glover F., E. Taillard, M. Laguna and D. de Werra, eds. Tabu Search, Annals of Operations Research 41, Baltzer, Basel, 1993

39
Goldberg D.E. Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989

40
Hiriart-Urruty J.-B. and C. Lemaréchal Convex Analysis and Minimization Algorithms A Series of Comprehensive Studies in Mathematics 306, Springer-Verlag, 1993

41
van Laarhoven P.J.M. and E.H.L. Aarts Simulated Annealing: Theory and Applications, Reidel, Dordrecht, 1987

42
Yang C.C. Relational Databases, Prentice-Hall, Englewood Cliffs, NJ, 1986


Index Page