Library

X
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
  • 2020-2024  (19)
  • 2020-2023  (4)
  • 2005-2009
  • 2023  (16)
  • 2023  (16)
  • 2020  (7)
  • 2020  (7)
Source
Years
  • 2020-2024  (19)
  • 2020-2023  (4)
  • 2005-2009
Year
Language
  • 1
    facet.materialart.
    Unknown
    A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance (2020)
    Details
    Publication Date: 2021-02-22
    Description: For providing railway services the company’s railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see Maroti and Kroon 2005, or Cordeau et. al. 2001 for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in Borndörfer et. al. 2015. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of Reuther 2017 that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 2
    facet.materialart.
    Unknown
    A Solution Approach to the Vehicle Routing Problem with Perishable Goods (2020)
    Details
    Publication Date: 2020-08-05
    Description: This paper focuses on a special case of vehicle routing problem where perishable goods are considered. Deliveries have to be performed until a due date date, which may vary for different products. Storing products is prohibited. Since late deliveries have a direct impact on the revenues for these products, a precise demand prediction is important. In our practical case the product demands and vehicle driving times for the product delivery are dependent on weather conditions, i.e., temperatures, wind, and precipitation. In this paper the definition and a solution approach to the Vehicle Routing Problem with Perishable Goods is presented. The approach includes a procedure how historical weather data is used to predict demands and driving times. Its run time and solution quality is evaluated on different data sets given by the MOPTA Competition 2018.
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 3
    facet.materialart.
    Unknown
    An FPTAS for Dynamic Multiobjective Shortest Path Problems (2020)
    Details
    Publication Date: 2021-04-12
    Description: We propose in this paper the Dynamic Multiobjective Shortest Problem. It features multidimensional states that can depend on several variables and not only on time; this setting is motivated by flight planning and electric vehicle routing applications. We give an exact algorithm for the FIFO case and derive from it an FPTAS, which is computationally efficient. It also features the best known complexity in the static case.
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 4
    facet.materialart.
    Unknown
    The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing (2020)
    Details
    Publication Date: 2022-03-14
    Description: The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances.
    Language: English
    Type: conferenceobject , doc-type:conferenceObject
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 5
    facet.materialart.
    Unknown
    Multi-period line planning with resource transfers (2020)
    Details
    Publication Date: 2023-08-02
    Description: Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 6
    facet.materialart.
    Unknown
    Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates (2023)
    Details
    Publication Date: 2023-09-05
    Description: The ongoing electrification of logistics systems and vehicle fleets increases the complexity of associated vehicle routing or scheduling problems. Battery-powered vehicles have to be scheduled to recharge in-service, and the relationship between charging time and replenished driving range is non-linear. In order to access the powerful toolkit offered by mixed-integer and linear programming techniques, this battery behavior has to be linearized. Moreover, as electric fleets grow, power draw peaks have to be avoided to save on electricity costs or to adhere to hard grid capacity limits, such that it becomes desirable to keep recharge rates dynamic. We suggest a novel linearization approach of battery charging behavior for vehicle scheduling problems, in which the recharge rates are optimization variables and not model parameters.
    Language: English
    Type: conferenceobject , doc-type:conferenceObject
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 7
    facet.materialart.
    Unknown
    Non-Linear Battery Behavior in Electric Vehicle Scheduling Problems (2023)
    Details
    Publication Date: 2023-10-04
    Description: The currently most popular approach to handle non-linear battery behavior for electric vehicle scheduling is to use a linear spline interpolation of the charge curve. We show that this can lead to approximate models that underestimate the charge duration and overestimate the state of charge, which is not desirable. While the error is of second order with respect to the interpolation step size, the associated mixed-integer linear programs do not scale well with the number of spline segments. It is therefore recommendable to use coarse interpolation grids adapted to the curvature of the charge curve, and to include sufficient safety margins to ensure solutions of approximate models remain feasible subjected to the exact charge curve.
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 8
    facet.materialart.
    Unknown
    K-Shortest Simple Paths Using Biobjective Path Search (2023)
    Details
    Publication Date: 2024-02-21
    Description: In this paper we introduce a new algorithm for the k-Shortest Simple Paths (K-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick (2012) that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar 2-SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice.
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 9
    facet.materialart.
    Unknown
    New Dynamic Programming Algorithm for the Multiobjective Minimum Spanning Tree Problem (2023)
    Details
    Publication Date: 2024-02-21
    Description: The Multiobjective Minimum Spanning Tree (MO-MST) problem is a variant of the Minimum Spanning Tree problem, in which the costs associated with every edge of the input graph are vectors. In this paper, we design a new dynamic programming MO-MST algorithm. Dynamic programming for a MO-MST instance leads to the definition of an instance of the One-to-One Multiobjective Shortest Path (MOSP) problem and both instances have equivalent solution sets. The arising MOSP instance is defined on a so called transition graph. We study the original size of this graph in detail and reduce its size using cost dependent arc pruning criteria. To solve the MOSP instance on the reduced transition graph, we design the Implicit Graph Multiobjective Dijkstra Algorithm (IG-MDA), exploiting recent improvements on MOSP algorithms from the literature. All in all, the new IG-MDA outperforms the current state of the art on a big set of instances from the literature. Our code and results are publicly available.
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 10
    facet.materialart.
    Unknown
    Targeted multiobjective Dijkstra Algorithm (2023)
    Details
    Publication Date: 2024-02-20
    Description: We introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. It is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. For any explored subpath, a label setting MOSP algorithm decides whether the subpath can be discarded or must be stored as part of the output. A major design choice is how to store subpaths from the moment they are first explored until the mentioned final decision can be made. The T-MDA combines the polynomially bounded size of the priority queue used in the MDA and alazy management of paths that are not in the queue. The running time bounds from the MDA remain valid. In practice, the T-MDA outperforms known algorithms from the literature and the increased memory consumption is negligible. In this paper, we benchmark the T-MDA against an improved version of the state of the art NAMOA∗drOne-to-One MOSP algorithm from the literature on a standard testbed.
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...