Mühendislik Fakültesi / Faculty of Engineering
Permanent URI for this collectionhttps://hdl.handle.net/11727/1401
Browse
12 results
Search Results
Item Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery: Mathematical Formulations and A Heuristic Algorithm(2015) Kececi, Baris; Altiparmak, Fulya; Kara, Imdat; 0000-0002-2730-5993; AAF-7020-2021; AAC-4793-2019; ABH-1078-2021; F-1639-2011One of the most important operational decisions in the logistics management is to determine the vehicle routes serving the customers. The Vehicle Routing Problem (VRP) can be defined as the determination of the optimal routes which meet the delivery (or pickup) demands from the depot to the customers. In the real life applications of logistics, vehicles in a fleet may differ from each other. In addition, the requirements arising from customers/goods may reveal the necessity to use different vehicles. Besides, companies do care more about the management of reverse flow of products, semi-finished and raw materials because of their economic benefits and as well as legal and environmental liabilities. In this paper, a variant of the VRP is considered with heterogeneous fleet of vehicles and simultaneous pickup and delivery. This problem is referred to Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery (HVRPSPD). The HVRPSPD can be defined as determining the routes and the vehicle types on each route while minimizing the total cost. In this paper, a polynomial sized flow-based mathematical model is proposed for the HVRPSPD. Since the HVRPSPD is in the class of NP-hard problems, it is difficult to find the optimal solution in a reasonable time even for the moderate size problems. Therefore, a simple and constructive heuristic algorithm is proposed to solve the medium and large scale HVRPSPD s. This algorithm is the adaptation of very well-known Clarke-Wright Savings approach, which has originally developed for the VRP, to the HVRPSPD. The performances of the proposed mathematical model and the heuristic algorithm have been examined on the test problems.Item The Location-Routing Problem with Simultaneous Pickup and Delivery: Formulations and A Heuristic Approach(2012) Karaoglan, Ismail; Altiparmak, Fulya; Kara, Imdat; Dengiz, Berna; 0000-0002-6023-6918; 0000-0003-1730-4214; AAG-4982-2019; AAF-7020-2021; ABH-1078-2021In this paper, we consider a variant of the Location-Routing Problem (LRP), namely the LRP with simultaneous pickup and delivery (LRPSPD). The LRPSPD seeks to minimize total cost by simultaneously locating the depots and designing the vehicle routes that satisfy pickup and delivery demand of each customer at the same time. We propose two polynomial-size mixed integer linear programming formulations for the problem and a family of valid inequalities to strengthen the formulations. While the first formulation is a node-based formulation, the second one is a flow-based formulation. Furthermore, we propose a two-phase heuristic approach based on simulated annealing, tp_SA, to solve the large-size LRPSPD and two initialization heuristics to generate an initial solution for the tp_SA. We then empirically evaluate the strengths of the proposed formulations with respect to their ability to find optimal solutions or strong lower bounds, and investigate the performance of the proposed heuristic approach. Computational results show that the flow-based formulation performs better than the node-based formulation in terms of the solution quality and the computation time on small-size problems. However, the node-based formulation can yield competitive lower bounds in a reasonable amount of time on medium-size problems. Meantime, the proposed heuristic approach is computationally efficient in finding good quality solutions for the LRPSPD. (C) 2011 Elsevier Ltd. All rights reserved.Item New Integer Linear Programming Formulation for the Traveling Salesman Problem with Time Windows: Minimizing Tour Duration with Waiting Times(2013) Kara, Imdat; Koc, Ozge Nimet; Altiparmak, Fulya; Dengiz, Berna; 0000-0003-1730-4214; ABH-1078-2021; ABH-1078-2021The travelling salesman problem, being one of the most attractive and well-studied combinatorial optimization problems, has many variants, one of which is called travelling salesman problem with Time Windows (TSPTW)'. In this problem, each city (nodes, customers) must be visited within a time window defined by the earliest and the latest time. In TSPTW, the traveller has to wait at a city if he/she arrives early; thus waiting times directly affect the duration of a tour. It would be useful to develop a new model solvable by any optimizer directly. In this paper, we propose a new integer linear programming formulation having O(n(2)) binary variables and O(n(2)) constraints, where (n) equals the number of nodes of the underlying graph. The objective function is stated to minimize the total travel time plus the total waiting time. A computational comparison is made on a suite of test problems with 20 and 40 nodes. The performances of the proposed and existing formulations are analysed with respect to linear programming relaxations and the CPU times. The new formulation considerably outperforms the existing one with respect to both the performance criteria. Adaptation of our formulation to the multi-traveller case and some additional restrictions for special situations are illustrated.Item Multi-Objective Optimization of A Stochastic Assembly Line Balancing: A Hybrid Simulated Annealing Algorithm(2011) Cakir, Burcin; Altiparmak, Fulya; Dengiz, Berna; 0000-0003-1730-4214; AAF-7020-2021This paper deals with multi-objective optimization of a single-model stochastic assembly line balancing problem with parallel stations. The objectives are as follows: (1) minimization of the smoothness index and (2) minimization of the design cost. To obtain Pareto-optimal solutions for the problem, we propose a new solution algorithm, based on simulated annealing (SA), called m_SAA, m_SAA implements a multinomial probability mass function approach, tabu list, repair algorithms and a diversification strategy. The effectiveness of m_SAA is investigated comparing its results with those obtained by another SA (using a weight-sum approach) on a suite of 24 test problems. Computational results show that m_SAA with a multinomial probability mass function approach is more effective than SA with weight-sum approach in terms of the quality of Pareto-optimal solutions. Moreover, we investigate the effects of properties (i.e., the tabu list, repair algorithms and diversification strategy) on the performance of m_SAA. (C) 2010 Elsevier Ltd. All rights reserved.Item Design Of Reliable Communication Networks: A Hybrid Ant Colony Optimization Algorithm(2010) Dengiz, Berna; Altiparmak, Fulya; Belgin, Onder; 0000-0003-1730-4214; 0000-0001-6702-2608; AAF-7020-2021; K-1080-2019This article proposes a hybrid approach based on Ant Colony Optimization (ACO) and Simulated Annealing (SA), called ACO_SA, for the design of communication networks. The design problem is to find the optimal network topology for which the total cost is a minimum and the all-terminal reliability is not less than a given level of reliability. The proposed ACO_SA has the advantages of the ability to find higher performance solutions, created by the ACO, and the ability to jump out of local minima to find better solutions, created by the SA. The effectiveness of ACO_SA is investigated by comparing its results with those obtained by individual application of SA and ACO, which are basic forms of ACO_SA, two different genetic algorithms and a probabilistic solution discovery algorithm given in the literature for the design problem. Computational results show that ACO_SA has a better performance than its basic forms and the investigated heuristic approaches.Item Buffer Allocation and Performance Modeling in Asynchronous Assembly System Operations: An Artificial Neural Network Metamodeling Approach(2007) Altiparmak, Fulya; Dengiz, Berna; Bulgak, Akif A.; 0000-0003-1730-4214; AAF-7020-2021This article investigates metamodeling opportunities in buffer allocation and performance modeling in asynchronous assembly systems ( AAS). Practical challenges to properly design these complex systems are emphasized. A critical review of various approaches in modeling and evaluation of assembly systems reported in the recently published literature, with a special emphasis on the buffer allocation problems, is given. Various applications of artificial intelligence techniques on manufacturing systems problems, particularly those related to artificial neural networks, are also reviewed. Advantages and the drawbacks of the metamodeling approach are discussed. In this context, a metamodeling application on AAS buffer design/performance modeling problems in an attempt to extend the application domain of metamodeling approach to manufacturing/assembly systems is presented. An artificial neural network ( ANN) metamodel is developed for a simulation model of an AAS. The ANN and regression metamodels for each AAS are compared with respect to their deviations from the simulation results. The analysis shows that the ANN metamodels can successfully be used to model of AASs. Consequently, one concludes that practising engineers involved in assembly system design can potentially benefit from the advantages of the metamodeling approach. (c) 2006 Elsevier B. V. All rights reserved.Item A Hybrid Simulated Annealing For A Multi-Objective Stochastic Assembly Line Balancing Problem(2008) Cakir, Burcin; Dengiz, Berna; Altiparmak, Fulya; Xia, GP; Deng, XQ; 0000-0003-1730-4214; AAF-7020-2021Asssembly line balancing is the problem of assigning tasks to the workstations, while optimizing one or more objectives without violating restrictions imposed on the line. In practice, task times may be random due to the worker fatigue, low skill levels, job dissatisfaction, poorly maintained equipment, defects in raw material, etc. When stochastic task times are taken consideration in assembly lines, balancing procedure is more complex due to the probability of incompleteness of stations times in a given cycle time. In this study, a multi-objective simulated annealing algorithm (m_SAA) is proposed for single-model, stochastic assembly line balancing problem with the aim of minimizing of smoothness index and total design cost. To obtain Pareto-optimal solutions, m_SAA implements tabu list and a multinomial probability mass function approach. The effectiveness of the proposed m_SAA is comparatively investigated using another SA using weight-sum approach on the test problems. Computational results show that m_SAA with multinomial probability mass function approach is more effective than SA with weight-sum approach in terms of quality of Pareto-optimal solutions.Item A General Neural Network Model for Estimating Telecommunications Network Reliability(2009) Altiparmak, Fulya; Dengiz, Berna; Smith, Alice E.; 0000-0003-1730-4214; 0000-0001-8808-0663; AAF-7020-2021; AAK-2318-2021This paper puts forth a new encoding method for using neural network models to estimate the reliability of telecommunications networks with identical link reliabilities. Neural estimation is computationally speedy, and can be used during network design optimization by an iterative algorithm such as tabu search, or simulated annealing. Two significant drawbacks of previous approaches to using neural networks to model system reliability are the long vector length of the inputs required to represent the network link architecture, and the specificity of the neural network model to a certain system size. Our encoding method overcomes both of these drawbacks with a compact, general set of inputs that adequately describe the likely network reliability. We computationally demonstrate both the precision of the neural network estimate of reliability, and the ability of the neural network model to generalize to a variety of network sizes, including application to three actual large scale communications networks.Item A cross entropy approach to design of reliable networks(2009) Dengiz, Berna; Altiparmak, Fulya; 0000-0003-1730-4214; AAF-7020-2021One of the most important parameters determining the performance of communication networks is network reliability. The network reliability strongly depends on not only topological layout of the communication networks but also reliability and availability of the communication facilities. The selection of optimal network topology is an NP-hard problem so that computation time of enumeration-based methods grows exponentially with network size. This paper presents a new solution approach based on cross-entropy method, called NCE, to design of communication networks. The design problem is to find a network topology with minimum cost such that all-terminal reliability is not less than a given level of reliability. To investigate the effectiveness of the proposed NCE, comparisons with other heuristic approaches given in the literature for the design problem are carried out in a three-stage experimental study. Computational results show that NCE is an effective heuristic approach to design of reliable networks. (C) 2008 Elsevier B.V. All rights reserved.Item A Mathematical Formulation And Heuristic Approach For The Heterogeneous Fixed Fleet Vehicle Routing Problem With Simultaneous Pickup And Delivery(2021) Kececi, Baris; Altiparmak, Fulya; Kara, Imdat; ABH-1078-2021This study considers a variant of the vehicle routing problem (VRP) called the heterogeneous VRP with simultaneous pickup and delivery (HVRPSPD). The HVRPSPD may broadly be defined as identifying the minimum cost routes and vehicle types. To solve the HVRPSPD, first, we propose a polynomial-size mixed integer programming formulation. Because the HVRPSPD is an NP-hard problem, it is difficult to determine the optimal solution in a reasonable time for moderate and large-size problem instances. Hence, we develop a hybrid metaheuristic approach based on the simulated annealing and local search algorithms called SA-LS. We conduct a computational study in three stages. First, the performance of the mathematical model and SA-LS are investigated on small and medium-size HVRPSPD instances. Second, we compare SA-LS with the constructive heuristics, nearest neigh-borhood and Clarke-Wright savings algorithms, adapted for the HVRPSPD. Finally, the performance of SA-LS is evaluated on the instances of the heterogeneous VRP (HVRP), which is a special case of the HVRPSPD. Computational results demonstrate that the mathematical model can solve small-size instances optimally up to 35 nodes; SA-LS provides good quality solutions for medium and large-size problems. Moreover, SA-LS is superior to simple constructive heuristics and can be a preferable solution method to solve HVRP and VRPSPD instances successfully.