Wyniki wyszukiwania - BazTech

1

A hybrid model of analytical network process and mixed-integer programming for selecting restaurant food supplier

Silalahi Agustinus, Sukwadi Ronald, Vanessa, Le Minh-Thai, Thu Nguyen Thi Bich

Mathematica Applicanda

|

2023

|

Vol. 51, no. 1

13--31

EN

Supplier selection is one of the essential processes of procurement in every business, including restaurants. Having good suppliers for restaurants is almost as important as having the best quality food. Many suppliers of food and beverages in Indonesia make it difficult for restaurant owners to choose the best. Therefore, determining the appropriate criteria for selecting suppliers and measuring the performance of suppliers is very crucial. This research aims to achieve maximum quality of raw material procurement in Sushi Man Restaurant, Kelapa Gading. The hybrid model is built using the Analytical Network Process (ANP) method and integrated with Mixed-Integer Programming (MIP) to be solved with Super Decision and LINGO software. The objectives of this hybrid model are to maximize performance and minimize procurement costs. The result shows that the optimum solution for salmon suppliers is PT. Indoguna Utama and PT. Ruangan Pendingin Indonesia, for chukka wakame’s supplier are PT. Indosps Bogatama Sukses and CV. Mulia Kencana, and for chukka idako’s supplier are PT. Indosps Bogatama Sukses and CV. Mulia Kencana. The other suppliers can still be used for the procurement in Sushi Man Restaurant, but their performance needs to be improved.

PL

Wybór dostawców jest jednym z podstawowych problemów decyzyjnych dla projektu wykorzystującego różne półprodukty i surowce. Widać to wyraźnie w przypadku restauracji. Posiadanie odpowiednich dostawców dla restauracji wiąże się z terminowym dostarczaniem surowców o odpowiedniej jakości. Wielu dostawców żywności i napojów w Indonezji utrudnia właścicielom restauracji wybór najlepszego. Dlatego ważne jest ustalenie odpowiednich kryteriów wyboru dostawców i ocena ich skuteczności. Przedstawione badania mają na celu osiągnięcie maksymalnej jakości pozyskiwanych surowców dla przykładowych restauracji. W artykule podano przykład restauracji: Sushi Man i Kelapa Gading. Do analitycznego modelowania problemu wykorzystano model hybrydowy. Model hybrydowy zbudowany jest metodą analitycznego procesu sieciowego (ANP), zintegrowanego z mieszanym programowaniem całkowitoliczbowym (MIP). Rozwiązanie problemu dla tak skonstruowanego modelu można przeprowadzić za pomocą dostępnego oprogramowania do rozwiązywania zadań badań operacyjnych. W przykładzie zawartym w pracy wykorzystano oprogramowanie: Super Decision oraz LINGO. Autorzy postawili sobie za cel maksymalizację efektywności dostawców i minimalizację kosztów zaopatrzenia. Zaprezentowane wyniki pokazują, jak praktycznie wykorzystać takie podejście do problemu.

2

Epidemiology-constrained Seating Plan Problem

Dąbkowski Jakub, Kacperski Przemysław, Kaleta Mariusz

Foundations of Computing and Decision Sciences

|

2022

|

Vol. 47, No. 3

235--246

EN

The emergence of an infectious disease pandemic may result in the introduction of restrictions in the distance and number of employees, as was the case of COVID-19 in 2020/2021. In the face of fluctuating restrictions, the process of determining seating plans in office space requires repetitive execution of seat assignments, and manual planning becomes a time-consuming and error-prone task. In this paper, we introduce the Epidemiology-constrained Seating Plan problem (ESP), and we show that it, in general, belongs to the NP-complete class. However, due to some regularities in input data that could affect computational complexity for practical cases, we conduct experiments for generated test cases. For that reason, we developed a computational environment, including the test case generator, and we published generated benchmarking test cases. Our results show that the problem can be solved to optimality by CPLEX solver only for specific settings, even in regular cases. Therefore, there is a need for new algorithms that could optimize seating plans in more general cases.

3

Mixed-integer programming formulations for the truck scheduling problem with fixed outbound departures

Wolff Pascal, Huo Jiazhen, Pfohl Hans-Christian

LogForum

|

2021

|

Vol. 17, no. 2

243--251

EN

Background: Truck scheduling at cross-docking terminals has received much academic attention over the last three decades. A vast number of mixed-integer programming models have been proposed to assign trucks to dock-doors and time slots. Surprisingly, only a few models assume fixed outbound truck departures that are often applied in the less-than-truckload or small parcel and express delivery industry. To the best of our knowledge, none of these papers explore whether a discrete-time or continuous-time model formulation has a better computational performance. This paper attempts to close this research gap and tries to shed light on which type of formulation is advantageous. Therefore, a variant of the truck scheduling problem with fixed outbound departures is considered. This problem's objective is to find a feasible truck schedule that minimizes the number of delayed freight units. Methods: We propose two model formulations for the described variant of the truck scheduling problem with fixed outbound departures. Specifically, the problem is formulated as a discrete-time and a continuous-time mixed-integer programming model. Results: A computational experiment is conducted in order to assess the computational performance of the presented model formulations. We compare the discrete-time and continuous-time formulation in terms of both the solution quality and computational time. Conclusions: The computational results show that the proposed discrete-time model formulation can solve problem instances of medium size to proven optimality within less than one minute. The continuous-time model formulation, on the other hand, can solve small instances to optimality. However, it requires longer solution times than the discrete-time formulation. Furthermore, it is unable to solve medium-sized instances within a 5-minute time limit. Thus, it can be summarized that the proposed discrete-time model formulation is clearly superior to the continuous-time model formulation.

PL

Wstęp: Harmonogramowanie przewozów oraz cross-dockingu leży w zasięgu zainteresowania uczonych już od ponad 30 lat. W tym okresie zaproponowało wiele różnych modeli programistycznych tablic awizacyjnych. Jednak zaledwie kilka modeli bierze pod uwagę stałe załadunki, które często są stosowane w przewozach niepełno samochodowych oraz kurierskich. Według naszego rozeznania, żaden z dostępnych modeli nie stosuje modelowania czasem w sposób dyskretny lub ciągły dla uzyskania lepszego wyniku. Celem pracy jest uzupełnienie tej luki w badaniach. Dlatego też rozważono wariant problemu harmonogramowania przewozów ze stałymi załadunkami z celem nadrzędnym znalezienia takiego sposobu harmonogramowania aby minimalizował on liczbę opóźnionych przewozów. Metody: Zaproponowano dwa modele, opisujące harmonogramowanie przewozów ze stałymi załadunkami. Problem ten został sformułowany poprzez model programistyczny ze zmienną czasu w ujęciu dyskretnym i ciągłym. Wyniki: Przeprowadzono symulację komputerową w celu określenie działania opracowanych modeli. Porównano wyniki pod względem jakości uzyskanego wyniku oraz niezbędnego czasu dla obliczeń. Wnioski: Na podstawie uzyskanych wyników można stwierdzić, że proponowany model dyskretny może rozwiązywać problem średniej wielkości w czasie niższej niż minuta. Model oparty na czasie ciągłym uzyskał z kolei optymalizację przy małych przypadkach. Wymagało to jednak dłuższego czasu obliczeniowego. Dodatkowo nie uzyskano dla rozwiązań średniej wielkości czasu niższego od 5 minut. Dlatego też wysunięto wniosek, że model dyskretny jest lepszym w porównaniu z modelem ciągłym.

4

Explicit modeling of multi-period setup times in proportional lot-sizing and scheduling problem with variable capacity

Kaczmarczyk Waldemar

Archives of Control Sciences

|

2021

|

Vol. 31, No. 4

883--912

EN

Small bucket models with many short fictitious micro-periods ensure high-quality schedules in multi-level systems, i.e., with multiple stages or dependent demand. In such models, setup times longer than a single period are, however, more likely. This paper presents new mixed-integer programming models for the proportional lot-sizing and scheduling problem (PLSP) with setup operations overlapping multiple periods with variable capacity. A new model is proposed that explicitly determines periods overlapped by each setup operation and the time spent on setup execution during each period. The model assumes that most periods have the same length; however, a few of them are shorter, and the time interval determined by two consecutive shorter periods is always longer than a single setup operation. The computational experiments show that the new model requires a significantly smaller computation effort than known models.

5

Comparing two pricing methods for path generation in a resilient network design problem

Kalesnikau I.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2017

|

nr 8-9

882--885, CD

EN

Global rerouting (GR) is a benchmark traffic routing and protection strategy for resilient communication networks that minimizes the protection capacity cost. In case of failure, GR restores traffic demands in the surviving link capacity from scratch, no matter how the nominal traffic flows have been routed. The considered optimization problem related to GR is formulated as a non-compact link-path linear program and as such requires path generation. The paper compares two versions of the pricing problem – an essential part of the path generation algorithm.

PL

Global rerouting (GR) jest strategią trasowania i zabezpieczania ruchu w sieciach telekomunikacyjnych, która minimalizuje koszt pojemności łączy wymaganej do odtwarzania przepływów. W przypadku awarii, GR realizuje przepływy w aktualnie dostępnych pojemnościach łączy od nowa, niezależnie od tego, jak te przepływy były trasowane przed awarią. Związany z GR problem optymalizacyjny jest sformułowany w postaci niezwartego programu liniowego typu łącze-ścieżka, który wymaga generacji ścieżek. W referacie porównane są dwie wersji tzw. pricing problem – podstawowej części algorytmu generacji ścieżek.

6

A random search algorithm for cyclic delivery synchronization problem

Gdowska K., Książek R.

LogForum

|

2017

|

Vol. 13, no. 3

263--272

EN

Background: The paper is devoted to the cyclic delivery synchronization problem with vehicles serving fixed routes. Each vehicle is assigned to a fixed route: the series of supplier’s and logistic centers to be visited one after another. For each route the service frequency is fixed and known in advance. A vehicle loads at a supplier’s, then it delivers goods to a logistic center and either loads other goods there and delivers them to the next logistic center along the route or goes to another logistic center. Each logistic center can belong to several routes, so goods are delivered there with one vehicle and then they departure for the further journey with another truck. The objective of this cyclic delivery synchronization problem is to maximize the total number of synchronizations of vehicles arrivals in logistic centers and their load times, so that it is possible to organize their arrivals in repeatable blocks. Methods: Basing on the previously developed mathematical model for the cyclic delivery synchronization problem we built a random search algorithm for cyclic delivery synchronization problem. The random heuristic search utilizes objective-oriented randomizing. In the paper the newly-developed random search algorithm for cyclic delivery synchronization problem is presented. Results: A computational experiment consisted of employing the newly-developed random search algorithm for solving a series of cyclic delivery synchronization problems. Results obtained with the algorithm were compared with solutions computed with the exact method. Conclusions: The newly-developed random search algorithm for cyclic delivery synchronization problem gives results which are considerably close to the ones obtained with mixed-integer programming. The main advantage of the algorithm is reduction of computing time; it is relevant for utilization of this method in practice, especially for large-sized problems.

PL

Wstęp: W pracy przedstawiono problem synchronizowania dostaw cyklicznych do centrów przeładunkowych. Dostawy realizowane są na stałych trasach: pojazd, obsługujący daną trasę ma dostarczyć towar do centrum przeładunkowego, załadować tam inny towar i przewieźć go do kolejnego punktu trasy lub wykonać pusty przejazd do punktu załadunku. Punktami synchronizacji obsługi tras są centra logistyczne, w których niejednokrotnie towar przywieziony przez jeden pojazd, wyrusza w dalszą drogę innym. Dostawy na każdej trasie realizowane są ze stałą częstotliwością. Trasy dostaw oraz ilości przewożonego towaru są znane. Celem w zadaniu synchronizacji dostaw cyklicznych jest maksymalizacja liczby synchronizacji przyjazdów i pobytu pojazdów w centrach logistycznych tak, aby możliwe było grupowanie ich obsługi w bloki rozładunkowo-załadunkowe. Metody: Na podstawie opracowanego wcześniej modelu matematycznego dla problemu synchronizowania dostaw cyklicznych do centrów przeładunkowych został zbudowany algorytm heurystyczny poszukujący rozwiązań poprzez ukierunkowane losowanie. W artykule przedstawiono opracowany algorytm losowego przeszukiwania. Wyniki: Eksperyment obliczeniowy polegał na rozwiązaniu zestawu zadań synchronizowania dostaw cyklicznych przy pomocy opracowanego algorytmu i porównaniu uzyskanych wyników ze znanymi rozwiązaniami dokładnymi. Wnioski: Przedstawiony algorytm heurystyczny dla zadania synchronizowania dostaw cyklicznych pozwala na uzyskanie rozwiązań zbliżonych do wyników otrzymanych przy zastosowaniu modelu programowania matematycznego. Zaletą zastosowanego algorytmu jest znaczne skrócenie czasu poszukiwania rozwiązania, co może mieć znaczenie dla praktycznego wykorzystania zaproponowanej metody.

7

The airport gate assignment problem – multi-objective optimization versus evolutionary multi-objective optimization

Kaliszewski I., Miroforidis J., Stańczak J.

Computer Science

|

2017

|

Vol. 18 (1)

41--52

EN

In this paper, we approach the Airport Gate Assignment Problem by Multi-objective Optimization as well as Evolutionary Multi-objective Optimization. We solve a bi-criteria formulation of this problem by the commercial mixed-integer programming solver CPLEX and a dedicated Evolutionary Multi-objective Optimization algorithm. To deal with multiple objectives, we apply a methodology that we developed earlier to capture decision-maker preferences in multi-objective environments. We present the results of numerical tests for these two approaches.

8

Hybrid Models for the OWA Optimization

Olender P.

Journal of Telecommunications and Information Technology

|

2016

|

nr 4

22--30

EN

When dealing with multicriteria problems, the aggregation of multiple outcomes plays an essential role in finding a solution, as it reflects the decision-maker's preference relation. The Ordered Weighted Averaging (OWA) operator provides a exible preference model that generalizes many objective functions. It also ensures the impartiality and allow to obtain equitable solutions, which is vital when the criteria represent evaluations of independent individuals. These features make the OWA operator very useful in many fields, one of which is location analysis. However, in general the OWA aggregation makes the problem nonlinear and hinder its computational complexity. Therefore, problems with the OWA operator need to be devised in an efficient way. The paper introduces new general formulations for OWA optimization and proposes for them some simple valid inequalities to improve efficiency. A hybrid structure of proposed models makes the number of binary variables problem type dependent and may reduce it signicantly. Computational results show that for certain problem types, some of which are very useful in practical applications, the hybrid models perform much better than previous general models from literature.

9

Energy-saving Algorithms for the Control of Backbone Networks: A Survey

Kamola M., Niewiadomska-Szynkiewicz E., Arabas P., Sikora A.

Journal of Telecommunications and Information Technology

|

2016

|

nr 2

13--20

EN

The rapid growth of energy demand by wired IP networks can be mitigated on hardware and software levels. While upgrading to more efficient transmission media still brings biggest savings, we take a look here at power-saving algorithms that combine the capability of setting networking equipment in arbitrary energy states which, combined with profound knowledge of the network traffic matrix, leads to considerable complex optimization problem formulations. Alternatively, lightweighted heuristic approaches are presented, built on much simpler network model but still capable to perform energy-efficient traffic engineering.

10

An optimal path planning problem for heterogeneous multi-vehicle systems

Klaučo M., Blažek S., Kvasnica M.

International Journal of Applied Mathematics and Computer Science

|

2016

|

Vol. 26, no. 2

297--308

EN

A path planning problem for a heterogeneous vehicle is considered. Such a vehicle consists of two parts which have the ability to move individually, but one of them has a shorter range and is therefore required to keep in a close distance to the main vehicle. The objective is to devise an optimal path of minimal length under the condition that at least one part of the heterogeneous system visits all desired waypoints exactly once. Two versions of the problem are considered. One assumes that the order in which the waypoints are visited is known a priori. In such a case we show that the optimal path can be found by solving a mixed-integer second-order cone problem. The second version assumes that the order in which the waypoints are visited is not known a priori, but can be optimized so as to shorten the length of the path. Two approaches to solve this problem are presented and evaluated with respect to computational complexity.

11

Cyclic delivery-scheduling problem with synchronization of vehicles' arrivals at logistic centers

Gdowska K. Z., Książek R.

LogForum

|

2015

|

Vol. 11, no. 4

341--350

EN

Background: In this paper a cyclic delivery-scheduling problem with vehicles serving fixed routes is presented. Each vehicle is assigned to one route to which some manufacturers' warehouses and logistics centers belong. A vehicle is to be loaded at a manufacturer's warehouse, then to deliver goods to a logistics center and may be also loaded there with other goods and to transport them to the next node along the route. One logistic center belongs to several routes, so the goods delivered by one vehicle may continue their journey by another truck. For every route the frequency of the vehicle is fixed and known. The objective here is to obtain such synchronization of vehicles arrivals in logistics centers, so that it is possible to organize their arrivals in repeatable blocks. Methods: In the paper the cyclic delivery-scheduling problem with vehicles serving fixed routes is formulated as a MIP model. Due to the fixed routes and desirable synchronization of vehicles arrivals in shared points this problem seems to be similar to the public transit network timetabling problem. Because of that the model presented here was based on a model dedicated to the public transit network timetabling problem, where optimization criterion was to maximize synchronization of vehicles' arrivals at the shared nodes. Results: Mixed integer programming model was employed for solving several cases of cyclic delivery-scheduling problem with vehicles serving fixed routes. Computational experiments are reported and obtained results are presented. Conclusions: The mixed integer programming model for the cyclic delivery-scheduling problem with synchronization of vehicles arrivals at logistic centers presented in this paper can be utilized for generating schedules for a group of vehicles serving fixed long routes. It may result in reducing total operational cost related to this group of vehicles as well as in reducing the goods travel time from the place of origin to their destination.

PL

Wstęp: W pracy przedstawiono problem harmonogramowania dostaw cyklicznych wykonywanych przez pojazdy obsługujące ustalone i niezmienne trasy. Każdy pojazd obsługuje inną trasę, gdzie ma za zadanie dostarczyć towar do centrum logistycznego, a także załadować tam inny towar i przewieźć go do kolejnego punktu trasy lub wykonać pusty przejazd do kolejnego punktu załadunku. Wspólnymi punktami tras pojazdów są centra logistyczne, w których niejednokrotnie towar przywieziony przez jeden pojazd, wyrusza w dalszą drogę następnym pojazdem z rozpatrywanej grupy. Przejazdy po każdej trasie realizowane są ze stałą częstotliwością. Celem dla wspomnianego problemu harmonogramowania dostaw cyklicznych jest uzyskanie synchronizacji przyjazdów i pobytu pojazdów w centrach logistycznych tak, aby możliwe było grupowanie ich obsługi w bloki. Metody: Ze względu na sztywno wyznaczone trasy oraz pożądaną synchronizację przyjazdów do punktów wspólnych tras problem ten wykazuje podobieństwo do problemów układania rozkładów jazdy komunikacji miejskiej. Dlatego przy konstruowaniu modelu matematycznego dla tego problemu wykorzystano model przygotowany pierwotnie dla zadania układania rozkładów jazdy komunikacji miejskiej z kryterium optymalizacji związanym z synchronizacją przyjazdów na przystanki wspólne. Wyniki: Eksperyment obliczeniowy polegał na rozwiązaniu i porównaniu uzyskanych wyników dla zbioru zadań programowania całkowitoliczbowego mieszanego dla problemu harmonogramowania cyklicznych dostaw z warunkiem synchronizacji przyjazdów do centrów przeładunkowych. Wnioski: Przedstawiony model MIP dla zadania harmonogramowania cyklicznych dostaw z warunkiem synchronizacji przyjazdów do centrów przeładunkowych może być wykorzystywany do tworzenia harmonogramów do planowania kursów cyklicznych wykonywanych przez grupę pojazdów obsługujących ustalone długie trasy. Pozwoli to na racjonalne planowanie pracy centrum logistycznego i pośrednio wpłynie na obniżenie kosztów, a także skrócenie czasu podróży towaru z punktu wysyłki do odbiorcy.

12

Optymalizacja technologii wytwarzania energii elektrycznej – symulacje programem eMix

Łyżwa W, Olek B., Wierzbowski M.

Rynek Energii

|

2014

|

Nr 6

25--32

PL

Artykuł dotyczy zagadnienia modelowania systemów energetycznych w celu obliczeń optymalnego miksu energetycznego dla określonego regionu lub kraju. Wyznaczenie optymalnego miksu energetycznego jest kluczowe dla określenia polityki energetycznej i może być realizowane przez dedykowane modele. W artykule dokonano przeglądu dostępnych narzędzi charakteryzując najbardziej powszechne kierunki rozwoju zagadnienia modelowania w energetyce. Przedstawiono również genezę powstania modelu optymalizacyjnego „eMix” opracowanego w Instytucie Elektroenergetyki Politechniki Łódzkiej wraz z zastosowaną metodologią. Model wykorzystuje programowanie binarne i całkowitoliczbowe (MILP, ang. mixed integer linear programming). Takie podejście jest najbardziej odpowiednie dla przedstawianego problemu, ponieważ w odróżnieniu od programowania liniowego pozwala nie tylko na określenie okresu budowy i czasu życia jednostek wytwórczych, ale także umożliwia uwzględnienie typoszeregów mocy jednostek wytwórczych, np. 450 MW, 900 MW. Na zakończenie zaprezentowano przykładowe wyniki obliczeń dla założonych scenariuszy.

EN

Paper focuses on the optimization of energy mix in the assumed region or country. The determination of energy mix is the crucial issue for designing the energy policy. It can be accomplished by dedicated models. The first part of the manuscript presents actual approaches for energy system modelling and introduction to the eMix model which is being developed at the Institute of Electrical Power Engineering at Lodz University of Technology. The second part concerns eMix model methodology. The model uses the mixed integer linear programming (MILP). In contrast to linear programming it allows for taking into account the wide database of available capacity for each technology, e.g. 450 MW, 900 MW. Finally the simulations results for the Polish power system are presented.

13

A mixed integer program for cyclic scheduling of flexible flow lines

Sawik T.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2014

|

Vol. 62, nr 1

121--128

EN

A new mixed integer programming formulation is presented for cyclic scheduling in flow lines with parallel machines and finite in-process buffers, where a Minimal Part Set (MPS) in the same proportion as the overall production target is repetitively scheduled. The cycle of parts in an MPS is not determined a priori, but is obtained along with the optimal schedule for all parts. In addition to the cyclic scheduling, a cyclic-batch scheduling mode is introduced, where within the MPS the parts of one type are processed consecutively. Numerical examples are included and some results of computational experiments are reported.

14

Optymalizacja doboru przekrojów kabli łączących turbiny w sieci wewnętrznej farmy wiatrowej

Wędzik A.

Przegląd Elektrotechniczny

|

2013

|

R. 89, nr 11

147-152

PL

W artykule, autor koncentruje się na problemie optymalnego doboru przekrojów kabli łączących turbiny i GPZ farmy wiatrowej. Pokazuje możliwości wykorzystania metody programowania całkowitoliczbowego, mieszanego z zastosowaniem zmiennych binarnych (Mixed Integer Programming - MIP), do rozwiązania takiego problemu. Artykuł jest próbą odpowiedzi na pytanie: jak połączyć turbiny, aby koszty całkowite, obejmujące koszty zakupu kabli i koszty strat energii czynnej, były najniższe? Przedstawia również praktyczne wnioski co do projektowania wewnętrznej sieci rozdzielczej SN farmy wiatrowej, wynikające z przeprowadzonych obliczeń i analiz.

EN

In the paper the author focuses on optimal sizing of MV cables linking wind turbines and the wind farm MV/HV substation. He shows the possibility of using the Mixed Integer Programming (MIP) method for solving the problem. The paper is an attempt to answer the question: how to connect together turbine towers minimizing capital expenditures, including the cables purchase costs and active energy losses cost? On the basis of conducted calculations and analyses, the author presents also practical recommendations for designing wind farm internal distribution networks.

15

Optimisation of telecommunications transport networks

Tomaszewski A.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2013

|

z. 189

9-190

EN

This monograph is devoted to optimisation models and algorithms for designing contemporary telecommunications transport networks. The particular focus is on the conceptual framework of transport network design and on the decomposition of the design problem and the design process. The presented conceptual framework is based on an original layered model of network resources, which is consistent with the functional architecture of transport networks contained in the ITU-T standards as well as can be directly expressed using mathematical models of multicommodity flow networks. The framework introduces an abstract generic model of the transport network design problem, its decomposition with respect to network layers and States, and an abstract generic network design procedure of solving the problem. The framework encompasses the models of the physical architecture and the organisational structure of the transport network. and the model of the network planning process. The presented work introduces an original complete mathematical description of the transport network based on the multicommodity network flow model complemented with elements pertaining to the notions of layers and states. Also, an original extension of the classical necessary and sufficient conditions of the existence of a multicommodity flow to the case of multiple layers and multiple slates is described. It is shown how the basic network model can be extended and generalised to consistently tackle fundamental phenomena and mechanisms of transport network operations related to traffic routing, network resilience to failures, quality of service and equitable allocation of network resources, variations and uncertainty of traffic demands, and network evolution. Applications of the basic methods of mathematical programming that are commonly used for network design are analysed in detail. In particular, the work analyses the branch-and-bound approach, the cutting plane method, the column generation and the constraint generation techniques of mixed integer linear programming, problem decomposition methods based on Benders' decomposition and Lagrangian relaxation, and the lesicographic maximization and max-min fair optimisation methods of multiple criteria decision making, The usage of the methods is analysed by means of original studies of difficult network optimization problems such as shortest-path routing design, connection restoration design in GMPLS networks, inter-domain traffic routing optimisation, and minimisation of label usage in GMPLS networks. A particularly important theoretical element of this work is a comprehensive analysis and classification of the complexity of designing transport networks resilient to failures. Original proofs of the NP-hardness of the resilient network design are presented that pertain to all major variants of the problem, in particular, providing a final answer to a number of so-far unresolved questions.

PL

Przedmiotem pracy są modele i algorytmy projektowania współczesnych telekomunikacyjnych sieci transportowych. Szczególną uwagę poświecono kwestii modelu pojęciowego problemu projektowania sieci oraz zagadnieniom dekompozycji problemu i procesu projektowania. Zaproponowany w pracy model pojęciowy jest oparty na oryginalnym warstwowym modelu zasobów sieci transportowej, który jest zgodny z podstawową architekturą funkcjonalną sieci transportowej zawartą w standardach 1TU-T poświęconych zagadnieniom sterowania i zarządzania sieciami, a jednocześnie może być wyrażony wprost poprzez modele optymalizacyjne sieci przepływów wielotowarowych. Elementami modelu pojęciowego są również model abstrakcyjnego generycznego problemu projektowania sieci transportowej dekomponowalnego wzglądem warstw i stanów sieci oraz abstrakcyjna generyczna procedura projektowania wielowarstwowej wielostanowej sieci transportowej. Uzupełnieniem modelu pojęciowego są modele architektury fizycznej i struktury organizacyjnej sieci transportowej, oraz model procesu planowania sieci. W pracy przedstawiono oryginalny kompletny opis matematyczny sieci transportowych oparty na modelu sieci przepływów wielotowarowych, uzupełnionym o pojęcia wielowarstwowości i wielostanowości. Zaprezentowano oryginalne rozszerzenie klasycznych warunków koniecznych i dostatecznych istnienia przepływu wielotowarowego na przypadek wielu warstw i wielu stanów sieci. Pokazano jak poprzez ograniczone rozszerzenia lub uogólnienia podstawego matematycznego opisu siec: jest możliwe jednolite zamodelowanie podstawowych zjawisk i mechanizmów działania sieci transportowej, związanych w szczególności z kierowaniem ruchu, zabezpieczeniem sieci przed awariami, zapewnieniem jakości obsługi ruchu i sprawiedliwym wykorzystaniem zasobów, zmiennością i niepewnością zapotrzebowani ruchowych oraz ewolucją sieci w czasie. Praca analizuje sposoby wykorzystania najważniejszych metod programowania matematycznego, w szczególności optymalizacji dyskretnej, stosowanych w projektowaniu sieci transportowych: metod programowania liniowego całkowitoliczbowego - metody podziałów i ograniczeń, metody płaszczyzn odcinających; metod dekompozycji - metody dekompozycji Bendersa, metody relaksacji Lagrange'a; metod optymalizacji wielokryterialnej – metod maksymalizacji leksykograficznej t optymalizacji sprawiedliwej. Przedstawiono oryginalne wykorzystanie tych metod w trudnych problemach projektowania sieci, takich jak problem kierowania ruchu po najkrótszych ścieżkach, problem projektowania sieci GMPLS zabezpieczonych mechanizmem Fast Reroute, problem kierowania ruchu międzydomenowego czy problem minimalizacji liczby etykiet w sieci GMPLS. Szczególnym elementem teoretycznym pracy jest wyczerpująca analiza i klasyfikacja złożoności problemów projektowania sieci zabezpieczonych przed awariami, której wynikiem jest zbiór oryginalnych dowodów NP-zupełność i wszystkich podstawowych wariantów problemu projektowania, w szczególności w części do niedawna nierozstrzygniętych.

16

Cyclic delivery scheduling to customers with different priorities

Gdowska K. Z., Książek R.

LogForum

|

2013

|

Vol. 9, no. 4

283--292

EN

Background: In this paper a cyclic delivery scheduling problem for customers with different priorities is presented. Shops, which are provided with deliveries, are occasionally located in places which are crucial for the proper flow of traffic. In such places coordination of deliveries is crucial; therefore it allows to completely eliminate the phenomenon of the simultaneous arrivals of suppliers. Methods: In this paper the cyclic delivery scheduling problem for customers with different priorities was presented. To this theoretical problem a mix integer programming model was developed. Specific approach to the cyclic delivery scheduling problem is inspired by timetabling problem for urban public transport. Results: Mixed integer programming model was employed for solving four cases of cyclic delivery scheduling problem for customers with different priorities. When the value of the synchronization priority assigned to a single customer raised then the total number of synchronizations in the whole network decreased. In order to compare solutions a synchronization rate was utilized. A simple factor was utilized - the proportion of number of synchronizations of deliveries to a given customer to the total number of synchronizations obtained for the whole network. When the value of synchronization priority raised then the value of synchronization rate of this customer improved significantly. Conclusions: The mixed integer programming model for the cyclic delivery scheduling problem for customers with different priorities presented in this paper can be utilized for generating schedules of serving customers located in places where only one delivery can be received and unloaded at one go and where there is no space for other suppliers to wait in a queue. Such a schedule can be very useful for organizing deliveries to small shops united in a franchising network, since they operate in a way that is very similar to the network presented in this paper. Moreover, in a franchising network it is possible to implement and control coordination between deliveries.

PL

Wstęp: W pracy przedstawiono problem harmonogramowania cyklicznych dostaw towarów do odbiorców o różnych priorytetach synchronizacji dostaw. Punkty handlowe, o których mowa w tym artykule, nierzadko są ulokowane przy ulicach, newralgicznych dla prawidłowego ruchu kołowego w mieście. W takich miejscach koordynacja dostaw do sklepów ma kluczowa znaczenie, gdyż zapobiega równoczesnym przyjazdom dostawców, a co za tym idzie tworzeniu utrudnień w ruchu. Metody: Problem harmonogramowania cyklicznych dostaw towarów do odbiorców o różnych priorytetach synchronizacji dostaw został sformułowany jako zadanie teoretyczne, dla którego zbudowano model programowania całkowitoliczbowego mieszanego. Specyficzne ujęcie problemu harmonogramowania dostaw cyklicznych było inspirowane problemem układania rozkładów jazdy miejskiej komunikacji publicznej. Wyniki: Eksperyment obliczeniowy polegał na rozwiązaniu i porównaniu uzyskanych wyników dla czterech zbudowanych zadań programowania całkowitoliczbowego mieszanego dla problemu cyklicznych dostaw do odbiorców o różnych priorytetach. Wraz ze wzrostem priorytetu dla jednego odbiorcy ogólna liczba synchronizacji dla całej sieci cyklicznych dostaw zmniejszyła się. W celu porównania jakości rozwiązań wyznaczono wskaźnik synchronizacji, rozumiany jako stosunek liczby synchronizacji dla danego odbiorcy do całkowitej ich liczby w rozwiązaniu dla danego zadania. Zastosowanie priorytetu synchronizacji dla odbiorcy spowodowało poprawę jego wskaźnika synchronizacji dostaw. Wnioski: Przedstawiony model programowania liniowego mieszanego dla zadania harmonogramowania cyklicznych dostaw z priorytetami dla odbiorców może być wykorzystywany do tworzenia harmonogramów dla dostawców produktów do odbiorców, u których występują ograniczenia związane z jednoczesnym obsługiwaniem kilku dostawców równocześnie.

17

Modelling Set-up Times Overlapping Two Periods in the Proportional Lot-Sizing Problem with Identical Parallel Machines

Kaczmarczyk W.

Decision Making in Manufacturing and Services

|

2013

|

Vol. 7, no. 1-2

43--50

EN

This paper presents a new mixed integer programming model for the Proportional Lot-Sizing Problem (PLSP) with identical parallel machines and set-up times overlapping two periods. The proposed model assumes constant period length and explicitly calculates the distribution of set-up operations among periods. The presented results of computational experiments with standard mip methods prove that the untying set-ups from period borders enables the reduction of the total costs in optimal solutions.

18

Overlay Multicast Optimization : IBM ILOG CPLEX

Kucharzak M., Zydek D., Poźniak-Koszałka I.

International Journal of Electronics and Telecommunications

|

2012

|

Vol. 58, No. 4

381-388

EN

IBM ILOG CPLEX Optimization Studio delivers advanced and complex optimization libraries that solve linear programming (LP) and related problems, e.g., mixed integer. Moreover, the optimization tool provides users with its Academic Research Edition, which is available for teaching and noncommercial research at no-charge. This paper describes the usage of CPLEX C++ API for solving linear problems and, as an exhaustive example, optimization of network flows in overlay multicast is taken into account. Applying continuous and integral variables and implementing various constraints, including equations and inequalities, as well as setting some global parameters of the solver are presented and widely explained.

19

An incremental approach for storage and delivery planning problems

Sakakibara K., Tian Y., Nishikawa I.

Decision Making in Manufacturing and Services

|

2012

|

Vol. 6, no. 1-2

5-23

EN

We consider a logistic planning problem for simultaneous optimization of the storage and the delivery. This problem arises in the consolidate shipment using an intermediate storage in a supply chain, which is typically found in the automobile industry. The vehicles deliver the items from the origin to the destination, while the items can be stored at some warehousing facilities as the intermediate storage during the delivery. The delivery plan is made for each day separately, but the storage at a warehouse may last for more than one day. Therefore, the entire logistic plan should be considered over a certain period for the total optimization. We formulate the storage and delivery problem as a mixed integer programming. Then, we propose a relax-and-fix type heuristic method, which incrementally fixes decision variables until all the variables are fixed to obtain a complete solution. Moreover, a semiapproximate model is introduced to effectively fix the variables. Based on the formulation, the delivery plan can be solved for each day separately. This has the advantage especially in the dynamic situation, where the delivery request is modified from the original request before the actual delivery day. Numerical experiments show that the simultaneous optimization gives the effective storage plan to reduce the total logistic cost, and the proposed heuristics efficiently reduce the computational time and are robust against the dynamic situation.

20

Przedstawienie wyników działania algorytmu genetycznego dla zadania CLSP planowania wielkości i szeregowania partii produkcyjnej

Książek R.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2011

|

T. 15, z. 2

291-297

PL

Poniższa praca opisuje wyniki uzyskane przy zastosowaniu algorytmu genetycznego w rozwiązaniu zadania programowania całkowitoliczbowego dla problemu planowania wielkości i szeregowania partii produkcyjnej. Spośród wielu modeli uwzględniających różne aspekty tego planowania wybrano model CLPS jako model bazowy dla wyznaczenia rozwiązania z wykorzystaniem zaimplementowanego algorytmu genetycznego. W pracy przedstawiono porównanie wyników działania algorytmu genetycznego z wynikami uzyskanymi dla PLCM.

EN

This paper presents the results obtained using a genetic algorithm to solve mixed integer programming task for the capacitated lot sizing problem. CLSP model was chosen from among many models with different variants of this problem as a basic for development of genetic algorithm. In this paper is summarized a comparison between the results of a genetic algorithm with the results of mixed integer programming for solving the same problem.