liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Combined vehicle routing and scheduling with temporal precedence and synchronization constraints
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
Norwegian School of Economics and Business Administration, Bergen.
2006 (English)In: EconPapers, Vol. 18Article in journal (Other academic) Published
Abstract [en]

We present a mathematical programming model for the combined vehicle routing and scheduling problem with time windows and additional temporal constraints. The temporal constraints allow for imposing pairwise synchronization and pairwise temporal precedence between customer visits, independently of the vehicles. We describe some real world problems where the temporal constraints, in the literature, usually are remarkably simplified in the solution process, even though these constraints may significantly improve the solution quality and/or usability. We also propose an optimization based heuristic to solve real size instances. The results of numerical experiments substantiate the importance of the temporal constraints in the solution approach. We also make a computational study by comparing a direct usage of a commercial solver against the proposed heuristic where the latter approach can find high quality solutions within distinct time limits.

Place, publisher, year, edition, pages
2006. Vol. 18
Keyword [en]
Routing; Scheduling; Temporal Constraints; Synchronization; Branch and Bound
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-13128OAI: diva2:17880
Available from: 2008-04-02 Created: 2008-04-02 Last updated: 2009-02-17
In thesis
1. Models and solution methods for large-scale industrial mixed integer programming problems
Open this publication in new window or tab >>Models and solution methods for large-scale industrial mixed integer programming problems
2007 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis deals with large-scale industrial problems that can be formulated using mixed integer linear programming (MIP) models. Because of the large problem size, it is not often possible to apply standard solution methods. Therefore special techniques must be used. In this thesis, both full optimization and optimization based heuristic approaches are developed.

The body of this thesis consists of five research papers. In the papers we consider industrial cases based on three applications: production planning at Södra Cell AB, ship routing and distribution at Södra Cell AB, and staff routing and scheduling in the Swedish home care.

We develop two large-scale MIP models for the production-planning problem. For solving, we use both a direct approach, and a combination of column generation and constraint branching. The latter is a technique to control the branching rules in a branch and bound framework and takes into account application specific properties.

For the ship routing problem, we present a MIP model and develop two solution methods. The first is based on an iterative rolling time horizon. In each step a part of the model is solved and later fixed. This is repeated until the full problem is solved. The second approach is to combine a genetic algorithm and linear programming. From the MIP model, we obtain solution bounds rarely present in genetic algorithm frameworks.

In the staff routing problem there are special synchronization constraints and we introduce a new MIP model. An exact solution approach based on column generation and branch and bound is developed. We also suggest a variable fixing heuristic, which we use for solving the more general problem with requirements on equal workload.

In the computational experiments, we use data instances obtained from real-world cases, and generated instances based on real-world cases. The numerical results show that high quality solutions can be obtained within reasonable time limits in all applications.

Place, publisher, year, edition, pages
Matematiska institutionen, 2007
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1071
Mathematic, linear programming (MIP), production-planning
National Category
urn:nbn:se:liu:diva-11454 (URN)978-91-85715-89-3 (ISBN)
Public defence
2007-02-16, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Available from: 2008-04-02 Created: 2008-04-02 Last updated: 2009-04-24

Open Access in DiVA

No full text

Other links

Link to discussion paperLink to Ph.D. thesis

Search in DiVA

By author/editor
Bredström, DavidRönnqvist, Mikael
By organisation
Optimization The Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 483 hits
ReferencesLink to record
Permanent link

Direct link