Tanker routing problem with fuzzy demands of served ships

The routing problem for tanker-refuellers is considered. The tankers start at the bunkering company and must serve several ships in different ports. In principle the modeling and algorithmic approaches for capacitated vehicle routing problems can be used. Since the demands of the ships are uncertain...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2009
Автори:	Werners, B., Kondratenko, Y.P.
Формат:	Стаття
Мова:	English
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2009
Теми:	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/12397
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Tanker routing problem with fuzzy demands of served ships / B. Werners, Y.P. Kondratenko // Систем. дослідж. та інформ. технології. — 2009. — № 1. — С. 47-64. — Бібліогр.: 24 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-12397
record_format	dspace
spelling	irk-123456789-123972013-02-13T02:45:19Z Tanker routing problem with fuzzy demands of served ships Werners, B. Kondratenko, Y.P. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи The routing problem for tanker-refuellers is considered. The tankers start at the bunkering company and must serve several ships in different ports. In principle the modeling and algorithmic approaches for capacitated vehicle routing problems can be used. Since the demands of the ships are uncertain and vague they are modeled using fuzzy sets. The first compromise solution can interactively be modified to meet the decision makers requirements with respect to the different criteria. The results are demonstrated using a small example. Розглядається проблема планування та оптимізації маршрутів танкерів-заправників, які стартують від бункерувальної компанії і мають забезпечити паливом судна, що розміщені в різних портах. Синтез алгоритмів оптимізації та моделювання здійснюється згідно з постановкою задачі планування маршрутів транспортних одиниць із обмеженою вантажомісткістю. При цьому інформація про замовлення суден в різних портах є неповною (невизначеною), значення замовлень суден моделюються з використанням нечітких множин. Перше компромісне рішення може бути модифіковане в інтерактивному режимі відповідно до декількох критеріїв та вимог оператора, що приймає рішення. Ефективність запропонованих алгоритмів підтверджується результатами моделювання. Рассматривается проблема планирования и оптимизации маршрутов танкеровзаправщиков, которые стартуют от бункеровочной компании и должны обеспечить допливом суда, расположенные в разных портах. Синтез алгоритмов оптимизации и моделирование осуществлены согласно постановке задачи планирования маршрутов транспортных единиц с ограниченной грузовместимостью. При этом информация о заказах судов в разных портах является неполной (неопределенной), значения заказов судов моделируются с использованием нечетких множеств. Первое компромиссное решение может модифицироваться в интерактивном режиме в соответствии с несколькими критериями и требованиями оператора, принимающего решения. Эффективность предложенных алгоритмов подтверждается результатами моделирования. 2009 Article Tanker routing problem with fuzzy demands of served ships / B. Werners, Y.P. Kondratenko // Систем. дослідж. та інформ. технології. — 2009. — № 1. — С. 47-64. — Бібліогр.: 24 назв. — англ. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/12397 62-50 en Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
topic	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
spellingShingle	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Werners, B. Kondratenko, Y.P. Tanker routing problem with fuzzy demands of served ships
description	The routing problem for tanker-refuellers is considered. The tankers start at the bunkering company and must serve several ships in different ports. In principle the modeling and algorithmic approaches for capacitated vehicle routing problems can be used. Since the demands of the ships are uncertain and vague they are modeled using fuzzy sets. The first compromise solution can interactively be modified to meet the decision makers requirements with respect to the different criteria. The results are demonstrated using a small example.
format	Article
author	Werners, B. Kondratenko, Y.P.
author_facet	Werners, B. Kondratenko, Y.P.
author_sort	Werners, B.
title	Tanker routing problem with fuzzy demands of served ships
title_short	Tanker routing problem with fuzzy demands of served ships
title_full	Tanker routing problem with fuzzy demands of served ships
title_fullStr	Tanker routing problem with fuzzy demands of served ships
title_full_unstemmed	Tanker routing problem with fuzzy demands of served ships
title_sort	tanker routing problem with fuzzy demands of served ships
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2009
topic_facet	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
url	http://dspace.nbuv.gov.ua/handle/123456789/12397
citation_txt	Tanker routing problem with fuzzy demands of served ships / B. Werners, Y.P. Kondratenko // Систем. дослідж. та інформ. технології. — 2009. — № 1. — С. 47-64. — Бібліогр.: 24 назв. — англ.
work_keys_str_mv	AT wernersb tankerroutingproblemwithfuzzydemandsofservedships AT kondratenkoyp tankerroutingproblemwithfuzzydemandsofservedships
first_indexed	2025-07-02T14:31:42Z
last_indexed	2025-07-02T14:31:42Z
_version_	1836545949857480704
fulltext	© B. Werners, Y.P. Kondratenko, 2009 Системні дослідження та інформаційні технології, 2009, № 1 47 TIДC ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ, ВИСОКОПРОДУКТИВНІ КОМП’ЮТЕРНІ СИСТЕМИ UDC 62-50 TANKER ROUTING PROBLEM WITH FUZZY DEMANDS OF SERVED SHIPS B. WERNERS, Y.P. KONDRATENKO The routing problem for tanker-refuellers is considered. The tankers start at the bun- kering company and must serve several ships in different ports. In principle the modeling and algorithmic approaches for capacitated vehicle routing problems can be used. Since the demands of the ships are uncertain and vague they are modeled using fuzzy sets. The first compromise solution can interactively be modified to meet the decision makers requirements with respect to the different criteria. The re- sults are demonstrated using a small example. 1. INTRODUCTION This paper deals with a very important routing problem in marine practice: the routing of tanker-refuellers (in the following called tankers) which provide bun- kering (transportation and unloading) operations for various ships. These ordering ships are located at different ports or, in general, at different points offshore. The importance of transportation is continuously growing due to the growing interna- tionalization of this business. Optimization models and methods are very appro- priate for transportation and distribution planning. This problem can be modeled by the so called capacitated vehicle routing problem (CVRP). The development of efficient models and algorithms to solve routing prob- lems is an important contribution of operations research to theory and practice. A lot of different approaches have been suggested and are applied to handle a wide spectrum of real world problems. An overview can be found in [4]. In particular, vehicle routing problems (VRP) with various modifications and different ap- proaches are considered [16]. Some of these approaches use methods to solve the traveling salesperson problem (TSP) as an integral part. A survey on TSP is given in [15]. Most of the VRP techniques can be applied successfully also to ship rout- ing problems [3, 9, 17, 19]. If the demand of the customers is not precisely known in advance deterministic and crisp models are not appropriate for decision sup- port. The VRP with stochastic demands of nodes is described in such publications as [1, 2, 5, 6, 8] but the efficient solution of SVRP (Stochastic Vehicle Routing Problem) presumes precise information about probability functions of the de- mands. To handle imprecise and vague information a fuzzy theory based ap- proach fits well. B. Werners, Y.P. Kondratenko ISSN 1681–6048 System Research & Information Technologies, 2009, № 1 48 In marine practice information about customers’ demands to be served can be uncertain too. Such kind of uncertain information characterizes the bunkering process (BP) by which ships are supplied with ordered fuel [14]. Usually the ship- owner sends an order for fuel supplying to the bunkering company using such uncertain terms as “approximately VALUE”, “about VALUE”, “between VALUE_1 and VALUE_2”, “at least VALUE”, “not less then VALUE”, “not more then VALUE”. The efficiency of the bunkering operations can be evaluated by the possibility to serve the orders with a minimum of consumption of own tanker’s fuel during delivery which depends on the total distance traveled by all tankers. A fuzzy set theoretical approach to the vehicle routing problem when de- mand at nodes is uncertain is considered in [19]. Their model is based on the well-known heuristic “sweeping algorithm” combined with a set of fuzzy rules and approximate reasoning to construct routes. They assume that every demand has to be served and that it is possible to return to the depot and then revisit the customer again. During the bunkering process considered here there is not enough time to travel twice. If the demand of a ship cannot be served completely during the planned trip the exceeding demand is lost. Therefore a fuzzy multi-criteria mathematical programming model is sug- gested here to solve the tanker routing problem with uncertain demands. An inter- active approach is used to find the compromise solution, which considers the minimal total distance of all routes necessary for all bunkering operations and the maximal potential total sales of fuel. For small problems it can be solved opti- mally by using standard mixed integer linear programming software. For larger problems an adequate heuristic has to be chosen. 2.1. GENERAL PROBLEM STATEMENT The port where the bunkering company is located is the only depot for the tank- ers. Here the orders are announced from the ship owners who know the respective demands of their ships approximately. The ships, which must be served by the tankers, have various capacities and different demands. Usually the captain of each ship orders the final crisp volume of fuel he needs at the moment when tanker and served ship meet in the j-th port, Nj ,,1…= . The decision maker of the bunkering company has to solve the tanker routing problem before bunkering operations start. At the depot 0 the bunkering company has K tankers for bunker- ing operations at its disposal. The tankers ( Kk ,,1…= ) are identical and they have the same capacity Cap to transport fuel. We suppose that the bunkers con- tain sufficient fuel for all demands of the N ships in the marine region and that the demand of each single ship is less or equal to the capacity of a tanker. Taking into account that the above-mentioned customers’ announcements for all ships to be served are uncertain the demand of each ship can be presented using a fuzzy set. We model the uncertain demand with triangular fuzzy numbers ( )jjjj dddd ,ˆ,~ = as shown in fig. 1 [7, 24]. The fuzzy number of each demand can be chosen based on the preliminary customer’s orders and the decision maker’s experience which deals with his or her intuition and the “a priori” knowledge about the type of ship, type of ship’s Tanker routing problem with fuzzy demands of served ships Системні дослідження та інформаційні технології, 2009, № 1 49 cargo, region of voyage, prescribed ports, ship’s captain decisions for analogous bunkering operations and others. The real world bunkering process with K tankers and N ships is parallel: each tanker serves all ships on its route which is planned by the decision maker at the bunkering company. The time period for the whole bunkering process is much shorter than in the case of an approach where the de- mands of all the ships must be served sequentially. The problem discussed in this paper deals with solving the tanker routing problem for fuzzy demands of served ships. A “compromise solution” for the spe- cific marine operations called “bunkering operations” is determined which takes into account the following goals: • maximum possible total quantity of unloaded fuel during the entire bun- kering process (this value is a main component defining bunkering company’s profit); • minimum possible total distance for tankers which serve ordering ships on all planned routes; • maximal possibility to serve the demand. The specific requirements for the bunkering process under consideration are: • each port j ( Nj ,,1…= ) is visited only once by only one tanker during the planning period for which the routes are designed and executed; • each tanker starts and finishes its route at the depot 0; • each demand jd at port j ( Nj ,,1…= ) is lower than the capacity Cap of a tanker; • there are enough tankers at the depot 0 to serve any total demand ∑∑ == ≤ N j j N j j dd 11 of all orders of the ships, Additionally, the locations of the depot and all ports with ordering ships, ca- pacity of the tanker, the distance resp. the traveling costs between the ports must be known. In the following a fuzzy multi-criteria programming approach is developed to solve the above stated problem. The decision maker interactively to improve the degree of satisfaction with the different goals can modify the compromise model. Fig. 1. Triangular membership function of the fuzzy demand jd of ship j jd jd̂ jd jd~µ B. Werners, Y.P. Kondratenko ISSN 1681–6048 System Research & Information Technologies, 2009, № 1 50 2.2. TANKER ROUTING PROBLEM WITH CRISP DEMANDS The problem is modeled as an extension of the one-depot capacitated vehicle routing problem which can be represented by the following model. Considering several trips to satisfy given demands at locations with tankers having restricted capacity available leads to the capacitated vehicle (here tanker) routing problem. Several models exist for this problem. In accordance with the above formulation the following model for the capacitated vehicle routing problem is chosen. The capacitated vehicle routing problem with well-known demand can be modeled considering two parts of constraints. One part containing constraints (2) and (3) is the generalized assignment problem. It groups cities to a tour consider- ing the respective demands and the capacity of the vehicles. The other part mod- els a traveling salesperson problem for each of these tours. This part contains con- straints (4) to (8). First we assume that the demand of each customer is exactly known in ad- vance and all other information is strictly given. The distribution starts from a single depot and the vehicle fleet is homogenous that is all vehicles have the same capacity. Considering different tours (vehicles, tankers) k ( Kk ,,1…= ) and cities (ports) ji, ( Nji ,,1, …= ) three types of variables are necessary: variable ijkx is binary with ⎩ ⎨ ⎧ = else0 ,touronfollowsfor1 kij xijk variable jky is binary with ⎩ ⎨ ⎧ = else0 ,tourtobelongscityfor1 kj y jk and variable jku is an integer 0≥ and for the optimal solution it is the sequence number of city j on trip k . Objective function of the classical vehicle routing problem is to minimize the total distance traveled: ∑∑∑ === K k ijkij N j N i xc 100 Min , (1) ijc for Nji ,,0, …= is the distance from city i to city j . The capacity Cap of the vehicle is sufficient to meet the crisp demand of all cities on tour k Kkyd N j jkj ,...,1forCap 1 =≤∑ = , (2) jd is the crisp demand at city j . Each city belongs to exactly one of the tours except city 0 with the depot ∑ = == K k jk Njy 1 ,...,1for 1 . (3) Tanker routing problem with fuzzy demands of served ships Системні дослідження та інформаційні технології, 2009, № 1 51 Each city j must be entered exactly once on the trip to which tour it belongs KkNjyx N i jkijk ,...,1,,...,0for 0 ===∑ = . (4) Each city i must be exited exactly once on the trip to which tour it belongs KkNiyx N j ikijk ,...,1,,...,0for 0 ===∑ = . (5) No city can follow itself on the tour KkNixiik ,...,1,,...,0for0 === . (6) Subtours are forbidden ( ) ijNjNiNxuu ijkikjk ≠==−−+≥ ,,...,1,,...,0for11 . (7) Each trip starts in the depot Nkuok ,...,1for1 == . (8) This is a mixed integer linear programming model. For small instances it can be solved exactly by using standard software. For larger instances a heuristic must be chosen. Constraint (7) is not the only formulation to avoid cycling and might cause difficulties when solving larger problems [17]. Some of the heuristics sug- gested in literature first group cities to tours and then solve the traveling salesper- son problem to optimize the respective routes. This vehicle routing model can be used to plan the routes for tankers, which are located in a depot and have to travel to different ports for bunkering. 2.3. EXAMPLE: TANKER ROUTING WITH CRISP DEMAND Let us consider a small example with 5 ships in different ports. The demand jd , 5,1…=j , for fuel is known (table 1). Several tankers are located in depot 0. The capacity of each tanker is 1000. Table 2 contains the distances ijc , Nji ,,0, …= , between the ports in miles. In this example jiij cc = holds for all Nji ,,0, …= . The optimal solution of the capacitated vehicle routing problem is calculated using the model (1) to (8) above and the software package ILOG AMPL CPLEX System vers. 7.0 (2000). The optimal routes 0 – 2 – 4 – 0 and 0 – 3 – 1 – 5 – 0 are shown in fig. 2. The total distance traveled is 340.2 miles. Because this graph is symmetric the tours 0 – 4 – 2 – 0 and 0 – 5 – 1 – 3 – 0 are optimal too. Exactly two tankers can serve the demands. T a b l e 1 . Demands of the ships j 1 2 3 4 5 dj 500 400 300 600 200 B. Werners, Y.P. Kondratenko ISSN 1681–6048 System Research & Information Technologies, 2009, № 1 52 T a b l e 2 . Distances between the ports 0 1 2 3 4 5 0 – 70.2 67.5 48.6 59.4 32.4 1 70.2 – 97.2 78.3 86.4 43.2 2 67.5 97.2 – 21.6 10.8 81 3 48.6 78.3 21.6 – 16.2 70.2 4 59.4 86.4 10.8 16.2 – 81 5 32.4 43.2 81 70.2 81 – 3.1. ROUTING PROBLEM WITH FUZZY DEMANDS If the demand at the different cities is uncertain and imprecise we suggest to model it using a fuzzy set theoretical approach and to use a fuzzy set jd~ , Nj ,,1…= , to represent the demand. The mathematical programming model is the same as above with the exception of capacity constraint (2). Instead of the crisp capacity constraint the following fuzzy constraint for the fuzzy demands on tour k has to be considered: Kkyd N j jkj ,...,1forCap~ 1 =≤∑ = (9) Kkyd N j jkj ,...1, = for ~D~ with 1 k ∑ = = . Modeling the fuzzy demand we suggest to consider the possibility that the actual demand of all ships on one tour is less or equal to the capacity of the tanker to a certain degree. Because of the following considerations this leads to a crisp equivalent model. This approach to handle these fuzzy constraints is similar to chance constraints programming in stochastic optimization. If the demand is not known exactly we suggest to find a solution for which the possibility to serve the Fig. 2. Optimal routing considering crisp demands Tanker routing problem with fuzzy demands of served ships Системні дослідження та інформаційні технології, 2009, № 1 53 demand is required at least to a certain degree [ ]1 ,0∈α . The decision maker has to determine α in advance. Considering a fuzzy number as a method of repre- senting uncertainty in a given quantity by defining a possibility distribution for the quantity is analyzed in [10]. An even stronger condition is to determine a cer- tain degree of necessity β that the demand on the tour can be served. That is [ ]Pos1 ,0,,...,1for)Cap~Pos 1 ∈=≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ≤∑ = αα Kkyd N j jkj (10) or even stronger [ ]1 ,0,,...,1for)Cap~Nec 1 ∈=≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ≤∑ = ββ Kkyd N j jkj . (11) If the fuzzy demand of each of the ships can be modeled using triangular fuzzy numbers a crisp equivalent formulation can be developed. For the calculation let us first consider the possibility and necessity of a triangular fuzzy number a~ to be greater or equal to zero [13]. ( ) { }( ) )( sup 0Pos0~Pos a 0 ~ xxxa x a µ ≥ =≥=≥ , (12) ( ) { }( ) { }( )0Pos10Nec0~Nec ~~ <−=≥=≥ xxxxa aa . (13) For a triangular fuzzy number ( ) aaaaaaaa ≠≠= ˆ and ˆ with ,ˆ ,~ these possibility (Pos) and necessity (Nec) can be determined using the following for- mulas ( ) ⎪ ⎪ ⎩ ⎪⎪ ⎨ ⎧ < ≤< − ≥ =≥ .00 ,0ˆ ˆ ,0ˆ1 0~Pos a aa aa a a a (14) ( ) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ < ≤< − ≥ =≥ .0ˆ0 ,ˆ0 ˆ ˆ ,01 0~Nec a aa aa a a a (15) Fig. 3. ( )0~Pos ≥a for a triangular fuzzy number a~ ( )0~Pos ≥a a â a B. Werners, Y.P. Kondratenko ISSN 1681–6048 System Research & Information Technologies, 2009, № 1 54 So the requirement for capacity in the above model can be determined as fol- lows Nkyd N j jkj ,...,1for )Cap~(Pos 1 =≥≤∑ = α , Nkyd N j jkj ,...,1for)0~Cap(Pos 1 =≥≥−⇔ ∑ = α . (16) If all demands ),ˆ,(~ jjjj dddd = , Nj ,,1…= are triangular fuzzy numbers then ∑ ∑ ∑ ∑ = = = = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−−=− N j N j N j N j jkjjkjjkjjkj ydydydyd 1 1 1 1 Cap, ˆCap,Cap ~Cap (17) is a triangular fuzzy number too. Thus the possibility that the capacity of the vehicle is sufficient to serve all demands kD~ on tour k is equal to ( ) ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≤< − − ≥ = ∑ ∑ ∑ ∑ ∑ ∑ = = = = = = N j jkj N j N j jkjjkjN j j N j jkj N j jkj k yd ydyd dd yd yd D 1 1 1 1 jkj 1 1 .< Cap0 ,ˆ Cap y )ˆ( Cap ,ˆ Cap1 ~ ServePos (18) The requirements for the necessity that the capacity is sufficient on tour k is ,,...,1for )Cap~Nec 1 Nkyd N j jkj = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ≥≤∑ = β .,...,1for)0~Cap(Nec 1 Nkyd N j jkj =≥≥−⇔ ∑ = β (19) It can be calculated similarly to Fig. 4. ( )0~Nec ≥a for a triangular fuzzy number a~ aa â ( )0~Nec ≥a Tanker routing problem with fuzzy demands of served ships Системні дослідження та інформаційні технології, 2009, № 1 55 .ˆ< Cap0 , Cap ˆ y )ˆ( ˆCap , Cap1 )~ Serve( Nec 1 1 1 1 jkj 1 1 ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≤< − − ≥ = ∑ ∑ ∑ ∑ ∑ ∑ = = = = = = N j jkj N j N j jkjjkjN j j N j jkj N j jkj k yd ydyd dd yd yd D (20) For every possibility and associated necessity measure and every set XA ⊂ the following implication is satisfied [13] 0)( Nec1)( Pos =⇒< AA . The consequence for our application is that it is more demanding to request the necessity to be greater than 0 than to request the possibility to be less or equal to 1. For 0 > α we can model the following constraints as crisp equivalents for the fuzzy constraint (9): ⇔≤α)~(ServePos kD ( ]∑ = ∈=≤−+ N j jkjj Kkydd 1 1,0 ,,,1 ,Cap ) )(1ˆ ( ααα … (21) respectively for 0 > β . ⇔≤ β)~(ServeNec kD ( ]∑ = ∈=≤−+ N j jkj Kkydd 1 j 1,0 ,,,1 ,Cap )ˆ )(1 ( βββ … . (22) To solve this fuzzy mathematical programming model we suggest to deter- mine the optimal solutions with respect to a given degree of possibility or even stronger a given degree of necessity that the capacity is sufficient to meet the total demand of the customers on each tour. If the decision maker is not able or does not want to require in advance a cer- tain degree of possibility or necessity for the demand served we suggest to give him or her additional information about the dependencies between those values and the minimal total distance the ships have to travel. On behalf of that first the model (1) and (3) to (8) with constraint (21) is solved with [ ]0,1∈α parametri- cally increasing from 0 to 1. Afterwards the second constraint (22) is included into the model instead of (21). It is stronger than (21) for every 0>β . Here too, [ ]0,1∈β is parametrically increased from 0 to 1. The parametrical modifications for this integer linear programming model exact a lot of calculations. Therefore it might be more efficient to calculate the maximal degree of possibility or necessity each time an optimal solution has been determined for the model. The next opti- mal solution can then be determined by improving this maximal degree by a small proportion and including this new value into the constraint. The result is an over- B. Werners, Y.P. Kondratenko ISSN 1681–6048 System Research & Information Technologies, 2009, № 1 56 view over all fuzzy efficient solutions with respect to minimal distance and maximal possibility respective necessity meeting the fuzzy demand. A solution is fuzzy efficient if it is not possible to improve one of the values without deteriorat- ing some of other ones [22, 23]. 3.2. EXAMPLE: TANKER ROUTING WITH FUZZY DEMANDS For demonstration purposes we again consider the tanker problem above but now the demands of the different ships are not exactly known. What the decision maker gets is an order d which is not binding and he has some experience what the demand might be. This is modeled using triangular fuzzy numbers ),ˆ,( = ~ dddd . For the small example the following data are to be considered with triangular fuzzy numbers for the uncertain demands. T a b l e 3 . Uncertain demands Ship No. 1 2 3 4 5 d 400 250 150 500 150 d̂ 500 400 300 600 200 d 600 500 350 800 400 The crisp equivalent model for a requested possibility 0.2 = α to serve the demand is solved by using CPLEX. The optimal solution of the mixed integer linear programming model are the two tours 0 – 3 – 2 – 4 – 0 and 0 – 1 – 5 – 0 with a total travel distance of 286.2. Parametric optimization is applied first with constraint set (21) and parame- ter [ ]1,0∈α and afterwards with constraint set (22) and parameter [ ]1,0∈β . This will give a general idea of efficient solutions with respect to total distance trav- eled and possibility or necessity to serve the demand. Solving the mixed integer linear programming model yields the following results: For the possibility α of serving the demand with 25.00 ≤≤α the optimal routes are 0 – 3 – 2 – 4 – 0 and 0 – 1 – 5 – 0 with a total distance of 286.2. For 125.0 ≤<α the optimal total distance is 340.2 and the optimal routes are 0 – 2 – 4 – 0 and 0 – 3 – 1 – 5 – 0 . Now the decision maker can decide whether he wants to accept the very small possibility 0.25 of meeting the demand with a total distance of 286.2 compared to a distance of 340.2 and a possibility of 1 to meet the requirements. The necessity to meet the demand with the above solution is 0. A higher necessity can be obtained by the optimal routes 0 – 5 – 1 – 0, 0 – 4 – 0 and 0 – 3 – 2 – 0 with a total distance of 402.3 and 3 tankers involved. This solution is — besides symmetrical ones - the only one with necessity greater than 0. Its ne- cessity to serve the demand is 1. Now the decision maker can decide which of these three different solutions fits his or her preferences best. Instead of parametrically varying degrees of possibility and necessity in the mathematical model it can be more efficient to determine the respective degree of possibility and necessity by calculations outside the mixed integer linear pro- Tanker routing problem with fuzzy demands of served ships Системні дослідження та інформаційні технології, 2009, № 1 57 gramming model (MILP). Starting with possibility 0 we get the optimal solution of the MILP model. This solution contains optimal tours with their fuzzy de- mands. Using this information the maximal possibility to meet the demand of this solution can be calculated by using (21) resp. (22) to calculate Pos (Serve kD~ ) resp. Nec (serve kD~ ) for each k , Kk ,,1…= , and then calculating )~(ServePos min 1= k K k D . For this example with 0)~Serve(Pos =kD the optimal routes are 0 – 3 – 2 – 4 – 0 and 0 – 1 – 5 – 0 with fuzzy demands )1650,1300,900(~ 1 =D and )1000,700,550(~ 2 =D and 25,0}1,25.0{min = . Then the MILP model is solved again with 25.0>α , e.g. 3.0=α . The results of both approaches are identical. They are shown in fig. 6. 4.1. FUZZY MULTI-CRITERIA APPROACH In general the bunkering company is not only interested in the possibility or even necessity of serving the demand but the company wants to sell as much fuel as possible. Sales is restricted by the demand and by the capacity of the tanker for a tour. A solution is preferable if the amount of the demand served is high. If the demand is known in advance the capacity constraint (2) ensures that there is Fig. 6. Dependency of total distance and possibility and necessity to serve the demand 25.00 ≤≤α 125.0 ≤<α 1,10 =≤≤ αβ Fig. 5. Optimal routes for different α resp. β B. Werners, Y.P. Kondratenko ISSN 1681–6048 System Research & Information Technologies, 2009, № 1 58 enough capacity for each tour to serve the entire demand and thus maximize sales. In the fuzzy environment considered here it is also possible to serve the entire demand. But here it means that so many tankers must travel so long distances that their capacity is high enough to meet every possible demand even if the member- ship degree is very low. Therefore these membership degrees have to be taken into account too. To maximize sales in this fuzzy context means to determine and maximize a fuzzy set which results from the fuzzy demand, the tour and the ca- pacity of the tanker. The fuzzy set sales kS~ on tour k depends o the minimum of the demand kD~ and the capacity of the tanker. The membership function can be calculated ( ) .Cap ,Cap Cap, 0 CapS~ Pos )( )( k ~ ~ > = < ⎪ ⎪ ⎩ ⎪⎪ ⎨ ⎧ ≥= x x xx x k k D S µ µ The membership function of the total demand to be served on all routes can be calculated by extended addition of the fuzzy sales. For the extension principle and extended operations see e.g. (Dubois and Prade, 1980; Zimmermann, 1992). The fuzzy total sales depended on the routes is with There are rather many calculations to be done to determine this fuzzy set. Therefore we suggest to use an easy to calculate defuzzification method. We sug- gest to use k N j jkj N j jkj N j jkj SDydydyd ~Cap,min 3 1Cap,ˆmin 3 1Cap,min 3 1 111 = ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ + ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ + ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ ∑∑∑ === (24) to determine a crisp approximation kSD~ for the sales on tour k and ∑ = K k kSD1 ~ as a crisp approximation of total sales. 4.2. EXAMPLE: MULTI-CRITERIA APPROACH In the example for the routes 0 – 3 – 2 – 4 – 0 and 0 – 1 – 5 – 0 the demands on the tours are as above and the capacity of each tanker is 1000. The membership function of the fuzzy demand to occur and to be served on tour 1 that is the mem- bership function of sales 1~Sµ is: ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ > = << − ≤ = .10000 ,10001 ,1000900 400 1300 ,9000 )(1~ x x xx x xSµ k K k S~1Σ = ( ){ }k K k zx S xz K k k k 1k S~1 ~ min sup )( µµ = =∑ ∑ = = . (23) Tanker routing problem with fuzzy demands of served ships Системні дослідження та інформаційні технології, 2009, № 1 59 It is shown in fig. 7. The fuzzy total sales for both routes is a fuzzy set with the membership func- tion depicted in fig. 8. The crisp approximation of the total sales is 717,1)000,1700550( 3 1)000,1000,1900( 3 1 ≈+++++ . 4.3. FUZZY MULTI-CRITERIA MODEL The fuzzy multi-criteria optimization model to be considered is ∑ ∑ ∑ = = = = N i N j K k ijkij xcuyxz 0 0 1 1 ),,( min , ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ = ∑∑ = Cap,~ni~m),,( max 1 K 1= 2 N j jkj k yduyxz , (25) Nkyd N j jkj ,...1,= 0~Cap Pos s.t. 1 α≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ≥−∑ = , Nkyd N j jkj ,...1,= 0~CapNec 1 β≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ≥−∑ = . Fig. 7. Membership function of sales 1 ~S µS1 Fig. 8. Membership function of total sales total sales µ 1 0.25 B. Werners, Y.P. Kondratenko ISSN 1681–6048 System Research & Information Technologies, 2009, № 1 60 and constraints (3) to (8) uyx ,, stand for the vectors of variables in this model. ni~m means the extended minimum of the two fuzzy sets kD~ and Cap. The crisp set Cap is considered as a fuzzy set with membership function 1Cap. We suggest to use the interactive approach developed by Werners [21,22,23] for the solution of this tanker problem with some modifications. Due to the fact that objective function (25) and constraints (16) resp. (19) are not independent of each other they should be handled differently and adequately. For (16) and (19) the crisp equivalent models (21) and (22) are used. The individual optimum of 1z i.e. the minimal total distance should be de- termined so that at least the lower bound of the fuzzy demand ∑∑ = = K k N j jkj yd 1 1 is served. The individual optimum of the objective “minimal total distance” is the solu- tion of the model ∑ ∑ ∑ N N K ijkij xc 0=i 0=j 1=k min , Kkyd jkj ,...1,= Cap s.t. N 1=j ≤∑ (26) and constraints (3) to (8). The optimal solutions are 1 ijkx , 1 jky and 1 jku , Nji ,,0, …= , Kk ,,1…= with 11111 )u , ,( zyxz = given by the solution algorithm and 2 1112 )u , ,( zyxz = to be calculated using (24). To determine the individual optimum of 2z the crisp equivalent model (24) instead of (25) is used. It is easy to prove that for demands ,~ jd Nj ,,1…= the maximum of (24) cannot exceed ∑ = ++N j jjj ddd1 )ˆ( 3 1 . In case that the number of vehicles is not restricted and each single demand is less than the capacity then a solution can be found which takes this value. So this individual optimum can be calculated without solving a mixed integer linear programming problem. But in general, there are several solutions which are not all fuzzy efficient. To determine a fuzzy efficient solution all solutions ( )222 ,, uyx have to be considered implic- itly and that one with ( )2221 ,, min uyxz has to be found. Those ( )222 ,, uyx which are optimal with respect to 2z all satisfy constraint (22) with 1=β . Thus, a fuzzy efficient individual optimum 2z can be ascertained by solving ∑ ∑∑ N i N j K k ijkij xc 0= 0= 1= min , Kkyd N j jkj ,...,1 Caps.t. 1 =≤∑ = (27) Tanker routing problem with fuzzy demands of served ships Системні дослідження та інформаційні технології, 2009, № 1 61 and constraints (3) to (8). The optimal solution is ( )222 ,, zyx with ( ) 22222 ,, zzyxz = and ( ) 1 2221 ,, zuyxz = . Now individual optimal and pessimistic solutions can be used to model membership functions for the two goals. ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ << − − ≤ = 1 * 1 1 * 11 11 * 11 * 11 ),,(0 ,),,( ),,( ,),,(1 )(1 zuyxz zuyxzz zz uyxzz zuyxz x z µ (28) and ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≤ << − − ≥ = .),,(0 ,),,( ),,( ,),,(1 )( 2 2 222 2 * 2 2 2 22 2 zuyxz zuyxzz zz zuyxz zuyxz x z µ (29) The first compromise model is λ max 1 0 0 1 11 )(z s.t. zxcz N i N j K k ijkij ≤+− ∑∑∑ = = = λ , (30) ⎜ ⎜ ⎝ ⎛ + ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ + ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ +− ∑∑∑ == −= Cap,ˆminCap,min 3 1)(z 111 22 N j jkj N j jk j K k ydydz λ 2 * 1 Cap,min zyd N j jkj ≥⎟ ⎟ ⎠ ⎞ ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ + ∑ = (31) and constraints (3) to (8), 10 ≤≤ λ . Constraints (16) and (19) can be omitted because they are implicitly con- tained in (31). One can get an equivalent linear model by substituting the following con- straints for the nonlinear constraint (31). ( ) 2 * 1 22 ˆ 3 1 ztttzz K k kk k ≥⎟ ⎠ ⎞ ⎜ ⎝ ⎛ +++− ∑ = − λ , (32) Kkydt jk N j jk ,...1,= 1 ∑ = −− ≤ , (33) Kkydt jk N j jk ,...1,= ˆˆ 1 ∑ = ≤ , (34) Kkydt jk N j jk ,...1,= 1 ∑ = ≤ , (35) B. Werners, Y.P. Kondratenko ISSN 1681–6048 System Research & Information Technologies, 2009, № 1 62 KkCapttt kk k ,...1,= ,ˆ,0 ≤≤ − . (36) 4.4. EXAMPLE: COMPROMISE SOLUTION Considering the small tanker routing example the following table shows the indi- vidual optimal solutions determined using models (1), (26), (3) to (8) for 1z and (1), (27), (3) to (8) for 2z . Both are efficient with respect to the two goals. T a b l e 4 . Individual optimal and pessimistic solutions Individual optimal routes 1z 2z 0–3–2–4–0 and 0–1–5–0 2,286 1 =z 1,717 2 =z 0–1–5–0 and 0–4–0 and 0–3–2–0 402,3 1 * =z 367,2 *2 =z This small example also demonstrates that the approach to calculate the in- dividual optimum of 2z straight forward is not appropriate. Maximizing the de- fuzzified version of (25) subject to constraints (3) to (8) without taking into ac- count the total distance leads to the following result. The optimal routes are 0 – 2 – 5 – 0 and 0 – 3 – 1 – 0 and 0 – 4 – 0 with identical possible sales of 2,367 but longer total distance of 497,1. The crisp compromise model is λ max 3,402116.1 s.t. 0 0 1 ≤+∑ ∑ ∑ = = = N i N j K k ijkij xcλ , ( ) 717,1ˆ 3 1+650 1= ≥++− ∑ K k kkk tttλ and constraints (33) to (36) and (3) to (8) and 10 ≤≤ λ . The optimal solution of the comprise model are the routes 0 – 1 – 5 – 0, 0 – 3 – 0 and 0 – 2 – 4 – 0, the membership degree is 19,00 ≈λ with 7,380z1 = and 933,1z2 ≈ . The possibility to serve the demand is 1 and the necessity is 0. The advantage of this solution is the higher possible sales compared with the routes 0 – 3 – 2 – 4 – 0 and 0 – 1 – 5 – 0 and even compared with 0 – 2 – 4 – 0 and 0 – 3 – 1 – 5 – 0 with possible sales 1,816 and a lower total dis- tance compared with 0 – 1 – 5 – 0, 0 – 4 – 0 and 0 – 3 – 2 – 0. Here the decision maker accepts the first compromise solu- tion, which is shown in fig. 9. Fig. 9. Compromise solution Tanker routing problem with fuzzy demands of served ships Системні дослідження та інформаційні технології, 2009, № 1 63 5. CONCLUDING REMARKS In this paper a fuzzy multi-criteria programming model is developed to solve the tanker routing problem with fuzzy demands. Using standard MILP software a compromise solution is determined which takes into account several criteria. One of the main advantages of this model is its generality. Additional aspects can be included into the model appropriately. Exemplarily the model can be extended to consider fuzzy distances between the ports. That can be necessary to model weather conditions. In case that the number of ships to be served is rather large then the model cannot be solved optimally and a heuristic has to be chosen. In principle the well known heuristic approaches can be used. Additional research is necessary to develop modifications which consider multiple criteria and find a compromise solution very efficiently. REFERENCES 1. Bertsimas D.J., SimchiLevi D. A new generation of vehicle routing research: Robust algorithms, addressing uncertainty // Operations Research. — 1996. — № 44. — P. 286–304. 2. Bertsimas D.J. A vehicle routing problem with stochastic demand // Operations Re- search. — 1992. — № 40. — P. 574–585. 3. Christiansen M. Decomposition of a combined inventory and time constrained ship routing problem // Transportation Science. — 1999. — №33. —P. 3–16. 4. Crainic T.G, Laporte G. Planning models for freight transportation // European Jour- nal of Operational Research. — 1997. — №97. — P. 409–438. 5. Dror M., Laporte G., Trudeau P. Vehicle Routing with Stochastic Demands: Proper- ties and Solution Frameworks // Transportation Science. — 1989. — № 23. — P. 166–176. 6. Dror M., Trudeau P. Stochastic vehicle routing with modified saving algorithm // European Journal of Operational Research. — 1986. — № 23. — P. 228–235. 7. Dubois D., Prade H. Fuzzy Sets and Systems: Theory and Applications. — Boston: Academic Press, Inc., 1980. — 393 p. 8. Gendrau M., Laporte G., Seguin R. An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers // Transportation Science. — 1995. — № 29. — P. 143–155. 9. Hanif D., Salem M.A.-Y., Merza M.H. Fleet management models and algorithms for an oil-tanker routing and scheduling problem // IIE Transactions. — 1999. — № 31. — P. 395–406. 10. Jamison K. David, Weldon A. Lodwick. Minimizing unconstraint fuzzy functions, Fuzzy Sets and Systems. — 1999. — № 103. — P. 457–464. 11. ILOG AMPL CPLEX System Version 7.0 User’s Guide, Incline Village, NV, 2000. — 69 p. 12. Kaufmann A., Gupta M.M. Introduction to fuzzy arithmetic: Theory and Applica- tions, Van Nostrand Reinhold, New York, 1991. — 384 p. 13. Klir G.J., Yuan B. Fuzzy Sets and Fuzzy Logic, Theory and Applications, Prentice Hall, Upper Saddle River, NJ, 1995. — 592 p. 14. Optimal Planning of Cargo Operations at Bunkering Tankers with Respect to Dynamical Character of Their Parameter Restrictions / Y.P. Kondratenko, G.F. Romanovsky, D.M. Pidoprygora G.V. Kondratenko // IFAC Conference on B. Werners, Y.P. Kondratenko ISSN 1681–6048 System Research & Information Technologies, 2009, № 1 64 Control Applications in Marine Systems, CAMS’04, July 7–9, 2004, Preprints, Universita Politecnica dellae Marche, Ancona, Italy. — P. 239–245. 15. Laporte G. The Traveling Salesman Problem: An overview of exact and approximate algorithms // European Journal of Operational Research. — 1992. — 59. — P. 231–248. 16. Laporte G. The Vehicle Routing Problem: An overview of exact and approximate algorithms // European Journal of Operational Research. — 1992. — 59. — P. 345–348. 17. Rana K., Vickson R.G. A Model and Solution Algorithm for Optimal Routing of Time-Chartered Containership // Transportation Science. — 1988. — № 22. — P. 83–95. 18. Schrage L. Optimization Modeling with LINGO. — Chicago, Illinois, 3rd Edition, 2000. — 534 p. 19. Teodorovic D., Pavkovic G. The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain // Fuzzy Sets and Systems. — 1996. — № 82. — P. 307–317. 20. Vukadinovic K., Teodorovic D. A fuzzy approach to the vessel dispatching problem // European Journal of Operational Research. —1994. — № 76. — P. 155–164. 21. Werners B. Interaktive Entscheidungsunterstützung durch ein flexibles mathema- tisches Programmierungssystem. — München: Minerva Publication, 1984. — 248 p. 22. Werners B. An interactive fuzzy programming system // Fuzzy Sets and Systems. — 1987. — № 23. — P. 131–147. 23. Werners B. Interactive multiple objective programming subject to flexible con- straints // European Journal of Operational Research. — 1987. — № 31. — P. 342–349. 24. Zimmermann H.-J. Fuzzy Set Theory — and Its Applications. — Boston/ Dordrecht/London: Kluwer Academic Publishers, 1992. Received 20.11.2007 From the Editorial Board: the article corresponds completely to submitted manuscript.

Tanker routing problem with fuzzy demands of served ships

Репозитарії

Схожі ресурси