Solving the logically constrained multiple choice multiple knapsack problem: A real case

In questa tesi viene analizzato un problema di ottimizzazione proposto da alcuni esercizi commerciali che hanno la necessita` di selezionare e disporre i propri ar- ticoli in negozio. Il problema nasce dall’esigenza di massimizzare il profitto com- plessivo atteso dei prodotti in esposizione, trovando per ognuno una locazione sugli scaffali. I prodotti sono suddivisi in dipartimenti, dai quali solo un ele- mento deve essere selezionato ed esposto. In oltre si prevede la possibilita` di esprimere vincoli sulla locazione e compatibilita` dei prodotti. Il problema risul- tante `e una generalizzazione dei gia` noti Multiple-Choice Knapsack Problem e Multiple Knapsack Problem. Dopo una ricerca esaustiva in letteratura si `e ev- into che questo problema non `e ancora stato studiato. Si `e quindi provveduto a formalizzare il problema mediante un modello di programmazione lineare intera. Si propone un algoritmo esatto per la risoluzione del problema basato su column generation e branch and price. Sono stati formulati quattro modelli differenti per la risoluzione del pricing problem su cui si basa il column generation, per individuare quale sia il piu` efficiente. Tre dei quattro modelli proposti hanno performance comparabili, mentre l’ultimo si `e rivelato piu` inefficiente. Dai risul- tati ottenuti si evince che il metodo risolutivo proposto `e adatto a istanze di dimensione medio-bassa.

Trajectory design of a multiple flyby mission to asteroids

In designing the trajectory for a multiple flyby mission to asteroids the choice of the targets is the most challenging problem. This dissertation faces this problem in the framework of the recently issued medium-size mission call (M5) from ESA: CASTAway. Starting from the preliminary work done in [6], this thesis develops a methodology for sequencing the potential targets in a multiple flyby mission. In order to reduce the computational time, the complete database of known small bodies is firstly pruned on the base of heuristic considerations. Using the assumption of small manoeuvres, a chief orbit concept could be used. Thus, two heuristic thresholds are defined in order to exclude non-promising targets given a chief orbit. The sequencing process takes chief orbit and promising targets as inputs and gives a set of candidate sequences. The results of such a process are analysed in the CASTAway framework and the best feasible sequence studied in details.