An order allocation problem with multiple-period and quantity discount

The outsourcing strategy of a company has a crucial role in its growth in an international context. The selection and the continuous maintenance of a successful business partnership can become extremely difficult to handle in a market where many external partners are available and every one has its own characteristics and contractual requirements. These concepts constitute the basics for what is known in literature as the Supplier Selection Problem, which is a procurement decision-making problem that aims to define methods and models to support the selection of a set of suppliers which improves the company competitiveness. In this thesis we consider the particular case of a generic big chain store which has to outsource its freight delivery services. We analyse two problems: in the first one the external partners use a cost which is constant per unit of volume, while in the second one some of them offer a cost discount depending on the quantity of service purchased. The challenge is to consider a very detailed cost structure and an hourly granularity of the demand, due to the characteristics of the external partners which can cover some kind of demand only during certain hours, within a planning horizon of several years. The cost structure, the two very different temporal levels and, especially, the extensiveness of the demand lead to huge instances, often intractable by commercial solvers. We formulate the two problems as Mathematical Programming models and we develop a solution approach based on column and row generation for each of them, in order to overcome the intractability issue. Finally, we analyse the results, which actually do not seem to identify the proposed solution approaches as clear winners. Nevertheless, the two approaches always provide a feasible solution, even when the solver does not.

La strategia di esternalizzazione di un’azienda ricopre un ruolo cruciale per la sua crescita in un contesto internazionale. La selezione ed il continuo mantenimento di un accordo commerciale di successo può diventare estremamente difficile da gestire in un mercato dove sono disponibili molti partner esterni e ognuno di essi ha le sue caratteristiche e i suoi requisiti contrattuali. Questi concetti costituiscono le basi per quello che in letteratura è conosciuto come il Supplier Selection Problem, che è un problema di decisione nel campo delle acquisizioni e il cui obiettivo è definire metodi e modelli per la selezione di un insieme di fornitori che migliori la competitività aziendale. In questa tesi consideriamo il caso particolare di una generica grande catena di negozi che deve esternalizzare i servizi di trasporto delle merci. Analizziamo due problemi: nel primo i partner commerciali utilizzano un costo per unità di volume costante, mentre nel secondo alcuni di essi offrono uno sconto che dipende dalla quantità di servizio acquistata. La sfida risiede nel considerare una struttura di costo dettagliata e una granularità fine della domanda di servizi, che è considerata a livello orario a causa delle caratteristiche dei partner commerciali che possono soddisfare alcuni tipi di domanda solo durante specifiche ore, in un orizzonte di pianificazione di alcuni anni. La struttura dei costi, i due livelli temporali molto differenti e, soprattutto, la capillarità della domanda portano ad avere istanze molto grandi, spesso intrattabili dai solver commerciali. Abbiamo formulato i due problemi come modelli di Programmazione Matematica e abbiamo sviluppato un approccio risolutivo basato sulla generazione dinamica di righe e colonne per ognuno di essi per superare la sfida dell’intrattabilità. Infine, abbiamo analizzato i risultati, che non sembrano in realtà identificare gli approcci risolutivi proposti come dei chiari vincitori. Ciononostante, i due approcci forniscono sempre una soluzione ammissibile, anche quando il solver non riesce.