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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Cost allocation in some routing problems: a game theoretic approach
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
2002 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In many situations a set of decision makers have the opportunity to cooperate. In this way they may reduce the total cost for satisfying their objectives. However, the reduction of cost is often not enough to motivate cooperation. The problem of how to divide the total cost (or gain) among the decision makers must also be solved.

This thesis include the modeling of cost allocation problems related to some routing problems. The cost allocation problems are formulated as cooperative games and we compute cost allocations based on concepts from cooperative game theory, such as the core and the nucleolus. 'We illustrate the problems using real-life data from Norsk Hydro. We consider how to divide the cost of an optimal traveling salesman tour among the customers that were served on a tour, and how to divide the cost of au optimal solution to a vehicle routing problem with a heterogeneous fleet among the customers served. These problems are formulated as a traveling salesman game and a vehicle routing game, respectively. For these games, we present procedures based on constraint generation to decide if the core is empty or not, and to compute the nucleolus.

One subproblem in the constraint generation procedures is a generalized multiple tour problem. In this problem each customer has a demand that either can be satisfied or not. If it is satisfied, revenue is collected and there are also travel costs to pay. A tabu search heuristic is used to identify which customers to serve and 011 which routes, with the objective to maximize the collected revenue minus the cost of traveling. We present numerical results based on a set of test instances.

We also consider the node weighted Steiner tree problem. In this problem there are costs associated with connecting the nodes of a network to a tree. In addition, there is a potential revenue to collect at each node, if it is connected. The problem is to decide which nodes to connect, and how, so as to maximize the revenue collected minus the connecting costs. For this problem, we suggest a Lagrangean-based heuristic to produce strong lower bounds and to obtain feasible solutions. We present numerical results based on a set of test instances.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2002. , p. 134
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 754Dissertations from the International Graduate School of Management and Industrial Engineering, ISSN 1402-0793 ; 61
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-143556ISBN: 9173733350 (print)OAI: oai:DiVA.org:liu-143556DiVA, id: diva2:1164864
Public defence
2002-05-14, C3, C-huset, Campus Linköping, Linköping, 10:15 (English)
Opponent
Available from: 2017-12-12 Created: 2017-12-12 Last updated: 2018-01-08Bibliographically approved

Open Access in DiVA

No full text in DiVA

By organisation
Department of MathematicsThe Institute of Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 32 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf