liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
Norwegian School of Economics and Business Administration (NHH), Bergen, Norway.
2007 (engelsk)Inngår i: Social Science Research Network, Vol. 7Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

In this paper we present a branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. The synchronization constraints are used to model situations when two or more customers need simultaneous service. The synchronization constraints impose a temporal dependency between vehicles, and it follows that a classical decomposition of the vehicle routing and scheduling problem is not directly applicable. With our algorithm, we have solved 44 problems to optimality from the 60 problems used for numerical experiments. The algorithm performs time window branching, and the number of subproblem calls is kept low by adjustment of the columns service times.

sted, utgiver, år, opplag, sider
2007. Vol. 7
Emneord [en]
Routing, Scheduling, Synchronization, Branch and Price
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-13129OAI: oai:DiVA.org:liu-13129DiVA, id: diva2:17881
Tilgjengelig fra: 2008-04-02 Laget: 2008-04-02 Sist oppdatert: 2009-04-15
Inngår i avhandling
1. Models and solution methods for large-scale industrial mixed integer programming problems
Åpne denne publikasjonen i ny fane eller vindu >>Models and solution methods for large-scale industrial mixed integer programming problems
2007 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Matematiska institutionen, 2007
Serie
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1071
Emneord
Mathematic, linear programming (MIP), production-planning
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-11454 (URN)978-91-85715-89-3 (ISBN)
Disputas
2007-02-16, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2008-04-02 Laget: 2008-04-02 Sist oppdatert: 2009-04-24

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Link to articleLink to Ph.D. Thesis

Personposter BETA

Bredström, DavidRönnqvist, Mikael

Søk i DiVA

Av forfatter/redaktør
Bredström, DavidRönnqvist, Mikael
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 619 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf