Heuristic solution approaches to the fixed charge transportation problem
Date
2019-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH SUMMARY : The classical transportation problem is concerned with the distribution of a single commodity
from a group of supply centres or sources, to a group of demand centres or destinations. The amount of commodity available at any source is limited, and the demand for the commodity at each destination is finite. Transportation cost functions may be non-linear because of quantity discounts, or price breaks, etc. Also, a fixed charge may be incurred every time units of commodity are sent from a given source to a given destination. The fixed charge transportation problems
(FCTP) differs from the standard linear transportation problem (TP) only in the nonlinearity (caused by die fixed charge) in the objective function.
Different heuristic methods were developed to generate initial solutions. The stepping stone method and tabu search algorithm are used to attempt to solve this problem. The algorithms are
evaluated according to their efficiency (computational runtime and solution quality) for solving FCTP problems. Comparisons are made using randomly generated benchmark instances from
the literature. The instances contain different sizes and different ranges of magnitude of fixed costs relative to variable costs. The primal-dual algorithm was also considered in finding good
solutions to be FCTP.
The results (for small instances) obtained for the proposed algorithm have been compared with that for an exact algorithm based on an integer programming formulation available in the literature.
The results from computational experiments show that the proposed algorithms yield near optimal solution to most instances. The primal-dual algorithm demonstrate significant
improvement over the proposed heuristic methods for small FCTPs, although it could not find feasible solutions to some instances.
AFRIKAANSE OPSOMMING : Die klassieke vervoerprobleem ondersoek die verspreiding van een soort gebruiksartikel vanaf 'n groep verskafferpunte of bronne na 'n groep aanvraagpunte of bestemmings. Die hoeveelheid van die gebruiksartikels beskikbaar by elke bron is beperk en die aanvraag by elke bestemming is eindig. Die vervoerkostefunksie mag nielineer wees as gevolg van grootmaatafslag, pryspunte ens. 'n Vaste koste kan ook gehef word elke keer wanneer gebruiksartikels van 'n gegewe bron na 'n gegewe bestemming vervoer word. Hierdie vaste koste vervoerprobleem (FCTP) verskil van die standaard lineere vervoerprobleem (TP) slegs in die nie-lineariteit (as gevolg van die vaste koste) in die doelfunksie. Verskillende heuristieke word voorgestel om beginoplossings te genereer. Die kringloopmetode saam met 'n tabusoektog word gebruik in 'n poging om hierdie probleem op die los. Die algoritmes word geevalueer in terme van hul effektiewiteit (berekeningstyd en oplossingskwaliteit). Die vergelykings word gemaak met lukraak gegenereerde probleme uit die literatuur. Hierdie gegenereerde probleme bevat verskillende groottes en verskillende verhoudings van vaste koste tot veranderlike koste. 'n Primaal-duaalalgoritme word ook aangebied om goeie oplossing vir die FCTP te vind. Die resultate (vir klein voorbeelde) wat vir die voorgestelede algoritmes verkry is, word vergelyk met die van die eksakte oplossing wat met 'n heeltallige programmeringsformulering beskikbaar in die literatuur verkry is. Die resultate wys dat die algoritmes in die meeste gevalle oplossings na-aan optimaal kry. Die primaal-duaalalgoritme verkry goeie verbeterings op die voorgestelede heuristieke vir FCTP's, maar kon nie in al die gevalle toelaatbare oplossings opspoor nie.
AFRIKAANSE OPSOMMING : Die klassieke vervoerprobleem ondersoek die verspreiding van een soort gebruiksartikel vanaf 'n groep verskafferpunte of bronne na 'n groep aanvraagpunte of bestemmings. Die hoeveelheid van die gebruiksartikels beskikbaar by elke bron is beperk en die aanvraag by elke bestemming is eindig. Die vervoerkostefunksie mag nielineer wees as gevolg van grootmaatafslag, pryspunte ens. 'n Vaste koste kan ook gehef word elke keer wanneer gebruiksartikels van 'n gegewe bron na 'n gegewe bestemming vervoer word. Hierdie vaste koste vervoerprobleem (FCTP) verskil van die standaard lineere vervoerprobleem (TP) slegs in die nie-lineariteit (as gevolg van die vaste koste) in die doelfunksie. Verskillende heuristieke word voorgestel om beginoplossings te genereer. Die kringloopmetode saam met 'n tabusoektog word gebruik in 'n poging om hierdie probleem op die los. Die algoritmes word geevalueer in terme van hul effektiewiteit (berekeningstyd en oplossingskwaliteit). Die vergelykings word gemaak met lukraak gegenereerde probleme uit die literatuur. Hierdie gegenereerde probleme bevat verskillende groottes en verskillende verhoudings van vaste koste tot veranderlike koste. 'n Primaal-duaalalgoritme word ook aangebied om goeie oplossing vir die FCTP te vind. Die resultate (vir klein voorbeelde) wat vir die voorgestelede algoritmes verkry is, word vergelyk met die van die eksakte oplossing wat met 'n heeltallige programmeringsformulering beskikbaar in die literatuur verkry is. Die resultate wys dat die algoritmes in die meeste gevalle oplossings na-aan optimaal kry. Die primaal-duaalalgoritme verkry goeie verbeterings op die voorgestelede heuristieke vir FCTP's, maar kon nie in al die gevalle toelaatbare oplossings opspoor nie.
Description
Thesis (MCom)--Stellenbosch University, 2019.
Keywords
Fixed charge transportation, Heuristic, Balinski, M. L., UCTD