Library

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
Source
Years
Keywords
Language
  • 11
    Publication Date: 2020-08-05
    Description: The Steiner tree packing problem (STPP) in graphs is a long studied problem in combinatorial optimization. In contrast to many other problems, where there have been tremendous advances in practical problem solving, STPP remains very difficult. Most heuristics schemes are ineffective and even finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this paper we review some “classical” STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by emplyoing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality.
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 12
    Publication Date: 2020-08-05
    Language: English
    Type: doctoralthesis , doc-type:doctoralThesis
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 13
    Publication Date: 2020-08-05
    Description: Ticket pricing in public transport usually takes a welfare maximization point of view. Such an approach, however, does not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and linear and integer programming. The ticket pricing problem is considered to be a constrained cost allocation game, which is a generalization of cost allocation games that allows to deal with constraints on output prices and on the formation of coalitions. An application to pricing railway tickets for the intercity network of the Netherlands is presented. The results demonstrate that the fairness of prices can be improved substantially in this way. A preliminary version of this paper appeared in the Proceedings of HPSC 2009 (Borndörfer and Hoang 2012). This journal article introduces better model and algorithms.
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 14
    Publication Date: 2020-11-17
    Description: Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.
    Language: English
    Type: conferenceobject , doc-type:conferenceObject
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 15
    Publication Date: 2020-08-05
    Description: Ticket pricing in public transport usually takes a welfare or mnemonics maximization point of view. These approaches do not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and integer programming. An application to pricing railway tickets for the intercity network of the Netherlands demonstrates that, in this sense, prices that are much fairer than standard ones can be computed in this way.
    Keywords: ddc:510
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Format: application/postscript
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...