1,720,965 research outputs found
A column generation algorithm for the multi-depot crew scheduling problem
No full textRisolvere il Multi-Depot Crew Scheduling Problem (MDCSP) significa trovare un insieme di turni per gli autisti degli autobus che soddisfino tutte le corse di una data tabella oraria minimizzando una data funzione
di costo. In questa tesi sono formulate istanze reali per la turnazione del personale come problemi di Set
Partitioning con vincoli aggiuntivi ed è stato implementato uno schema di generazione di colonne per risolverlo euristicamente. I vincoli aggiuntivi modellano principalmente le diverse tipologie di turno e le
associazioni tra i turni e i depositi che sono regolate da scelte interne delle aziende e che non possono essere
modificate. Il problema di pricing consiste nel trovare un cammino minimo con vincoli di risorsa su un grafo diretto aciclico ed è stato risolto con l’implementazione di uno schema di Branch and Bound con
rilassamento lagrangiano. Il grafo diretto aciclico modella le compatibilità tra le corse e, dando pesi appropriati agli archi, i costi operativi per la loro esecuzione in sequenza. In uno schema di generazione di
colonne un ruolo importante è ricoperto dalla fase di inizializzazione del problema e nel MDCSP un insieme di turni deve essere inserito nel modello di Set Partitioning per ottenere una soluzione ammissibile iniziale.
In questa tesi sono stati studiati e proposti tre modi per inizializzare e il problema con un’analisi dei pro e dei
contro. L’ordinamento topologico è una caratteristica di un grafo diretto aciclico ed è ampiamente spiegata in questa tesi e usata nello sviluppo dell’algoritmo. Il successo di uno schema di generazione di colonne dipende molto dal modo con cui è risolto il problema di pricing. Per migliorare quindi le prestazione globali
dell’algoritmo molte tecniche per l’incremento delle performance sono state implementate aumentando la
velocità d’esecuzione, l’efficienza e a qualità delle soluzioni trovate. L’algoritmo è stato sviluppato con un
struttura scalabile in modo tale da poter aggiungere ulteriori algoritmi di pricing. In questo modo se si riuscisse a implementare un algoritmo di pricing più performante o un algoritmo più efficiente fosse necessario per una particolare versione del MDCSP questa può essere tranquillamente aggiunta e utilizzata
nell’attuale struttura dell’algoritmo. Molti test sono stati eseguiti su piccole medie e grandi istanze e
un’analisi dei risultati ottenuti sono stati presentati nell’ultimo capitolo della tesi. I risultati computazionali
ottenuti esprimono la bontà dell’algoritmo rispetto alla qualità delle soluzioni e ai tempi d’esecuzione.
L’algoritmo è stato in grado di risolvere in tempi ragionevoli istanze grandi e in meno di un secondo le
istanze piccole.The goal on solving the Multi-Depot Crew Scheduling Problem (MDCSP) is to find a set of duties for the
bus drivers that satisfies all the trips of a given timetable at the minimum cost. In this thesis we modeled a
real MDCSP as a Set Partitioning Problem with side-constraints and we implemented a column generation
scheme to heuristically solve it. The side constraints mainly model the different types of duties and the
association between duties and depots ruled by laws and organizational choices that cannot be changed. The
pricing problem consisted of finding a Resource Constrained Shortest Path (RCSP) on a Directed Acyclic
Graph (DAG) and has been solved with a Branch and Bound scheme with Lagrangian relaxation. The DAG
modeled the compatibilities between the trips and, giving appropriate weights on the arcs, the operative cost
on them. In a Column Generation (CG) scheme an important role is played by the initialization phase in
which a set duties have to be nested in the MDCSP model in order to get an initial feasible solution. Three
ways to initialize the problem has been investigated and pros and cons of each of them are presented in the
thesis. The topological ordering is a characteristic of the DAG and is widely explained in this work and used
in the algorithm developed. The success of a CG relies mostly in the way the pricing problem is solved so
many performance improvement techniques have been implemented in order to make the algorithm faster,
more efficient and able to find better solution during the pricing phase. The algorithm has been developed
following a scalable structure able to insert in it more pricing algorithms. In this way if a more performing
algorithm will be implemented or a more suitable algorithm for a particular version of the MDCSP can be
used the software structure can easily host the new procedure. Many tests have been performed on small,
medium and big real instances and a comparison of the results obtained have been presented on the last
chapter of the thesis. The computational results obtained expressed the goodness of the algorithm in terms of
solution quality and computational time. It was able to solve big instances in a reasonable amount of time
and small instances in less than a second
A column generation approach for the multiple depot crew scheduling problem: a case study
Full text linkA Model-Based Approach for the Long Term Planning of Distributed Energy Systems in the Energy Transition
No full textEnergy system models need to adapt to better represent the new challenges brought by a changing scenario regarding technologies development and policy making. The mixed integer linear programming based approach proposed in this study wishes to handle the impacts of these changes on potential investments in distributed energy systems, whose design is to be determined for a time horizon lasting several years with parameters that might change even substantially in such timespan. In order to test the approach, a scenario representing a residential district with high penetration of electricity production from non controllable sources (photovoltaic panels) is used as a test case. The investment decision under examination is when to possibly deploy a battery system to deal with the production surplus generated during the day by the mismatch in production and demand. While electricity can be fed into the grid by taking advantage of a feed-in tariff scheme, this could not be the most economically favorable approach due to the dropping costs of the Lithium-ion battery systems in the near future. Results show that for the case study under analysis investing into batteries appears not convenient in terms of overall costs, although the best alternative solution provided with storage systems is only slightly more expensive
A Matheuristic for the Design and Management of Multi-energy Systems
No full textNew technologies and emerging challenges are drastically changing how the energy needs of our society have to be met. By consequence, energy models have to adapt by taking into account such new aspects while aiding in decision making processes of the design of energy systems. In this work the problem of the design and operation of a multi-energy system is tackled by means of a mixed integer linear programming (MILP) formulation. Given the large size of the problem to be solved, a matheuristic approach based on constraint relaxations and variable fixing is proposed in order to not restrict the applicability to small cases. Two variable fixing policies are presented and performance analysis comparison on them has been done. Tests have been performed on small and realistic instances and results show the correctness of the approach and the quality of the heuristic proposed in term of solution quality and computational time
Shelf space re-allocation for out of stock reduction
No full textAn ILP formulation is proposed for Shelf space re-allocation problem.Out-of-stock data are collected from the Shelf Detector System in real time.Space elastic demand function is linked with real-time statistical data.Tests performed on real, random and large instances. A planogram is a detailed visual map that establishes product positions over a shelf in a retail store. It is designed to support an innovative merchandising approach, to increase sales and profits, to supply the best location of a product for suppliers and to better manage the shelves. Product selection and the shelf space reserved to each product is a central activity for retailers and Shelf Out of Stock (SOOS) events are often strongly related to planogram design. In this paper we present a solution to optimally re-allocate shelf space to minimize Out of Stock (OOS) events. The approach uses SOOS data coming in real time from a sensor network technology, named Shelf Detector System, and an Integer Linear Programming model that integrates a space elastic demand function. Experimental results, based on a real scenario in the diaper category in Belgium, have proved that the system can efficiently calculate a proper solution able to re-allocate space and reduce OOS events
A computational study on the duty generation for the multi-depot bus driver scheduling problem
No full textA Heuristic for a Rich and Real Two-dimensional Woodboard Cutting Problem
No full textCutting operations in manufacturing are characterized by practical requirements and utility criteria that usually increase the complexity of formulations or, even worse, are difficult to be modeled in terms of mathematical programming. However, disregarding or just simplifying those requirements often leads to solutions considered not attractive or even useless by the manufacturer. In this paper we consider a rich two-dimensional cutting stock problem that covers the whole specification of a family of wood cutting machines produced by a worldwide leader in industrial machinery manufacturing. A sequential value correction heuristic is implemented to minimize the employed stock area while reducing additional objective functions
- …
