Browsing by Author "Kara, Imdat"

Now showing 1 - 18 of 18

Formulations for Minimizing Tour Duration of the Traveling Salesman Problem with Time Windows
(2015) Kara, Imdat; Derya, Tusan; ABH-1078-2021
Traveling Salesman Problem with Time Windows (TSPTW) serves as one of the most important variants of the Traveling Salesman Problem (TSP). The main objective functions expressed in the literature of the TSPTW consist of the following: (1) to minimize total distance travelled (or to minimize total travel time spent on the arcs), (2) to minimize total cost of traveling on the arcs and cost of waiting before services, or (3) to minimize total time passed from depot to depot (tour duration). When the unit cost of traveling and unit cost of waiting appear equal, then one may solve the problem just minimizing tour duration. According to our best knowledge, only one formulation with nonlinear constraints considers the aim of minimizing tour duration for symmetric case. However, for just minimizing tour duration, we haven't seen any linear formulation for symmetric and any general formulation for asymmetric TSPTW. In this paper, for minimizing tour duration, we propose polynomial size integer linear programming formulation for symmetric and asymmetric TSPTW separately. The performances of our proposed formulations are tested on well-known benchmark instances used to minimize total travel time spent on the arcs. For symmetric TSPTW, our proposed formulation sufficiently and capably finds optimal solutions for all instances (the biggest are with 400 customers) in an extremely short time with CPLEX 12.4. For asymmetric TSPTW, we used instances generated from a real life problem which were used for minimizing total arc cost. We used these instances for minimizing tour duration and observe that, optimal solutions of the most of the instances up to 232 nodes are obtained within seconds. In addition, the proposed formulation for asymmetric case obtained 7 new best known solutions. (C) 2015 The Authors. Published by Elsevier B.V.
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-2011
One 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.
An Integrated Fuzzy TOPSIS-Knapsack Problem Model for Order Selection in a Bakery
(2017) Ic, Yusuf Tansel; Ozel, Melis; Kara, Imdat; 0000-0001-9274-7467; AGE-3003-2022; ABH-1078-2021
In this study, a new model has been developed for the order selection problem for a bakery firm located in Turkey. We consider a combined order selection and process planning problem where a make-to-order bakery goods producer firm has to determine a set of orders to process so as to maximize the total profit. The developed model combines setup costs, sales price, lot size, demand and other important daily data of the products. After collecting the related data, fuzzy TOPSIS method is used to obtain the rankings of the orders (bread types). Then, the ranking scores are incorporated in the knapsack problem to determine the lot size and which orders to select. A computer application is also provided in the paper. With the help of MS Excel Visual Basic program, the computer application updates data daily, ranks the products, determines the lot size, and helps the decision maker with the selection of orders. The computational results show that the proposed method presented better results than the current method applied in the firm. Comparing the two methods in terms of cost reduction, the proposed method gives better results than the current method with 27%. Furthermore, the proposed computer program does not need extra special software or a commercial computer program, which is favorable for small-size enterprises.
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-2021
In 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.
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-2021
This 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.
A multiobjective mathematical model to form the best team at sports clubs: team harmony and player performance objectives
(2022) Budak, Gercek; Kara, Imdat
Purpose Team coaches of sports clubs are highly concerned when forming the best team to win the upcoming match at the stage before that particular game. Even if a team squad is comprising of a limited number of players, the combination of them makes a complicated problem with a huge number of possible line-ups. This study aims to build a mathematical model to solve this problem with the objectives of maximum player performance and team harmony. Design/methodology/approach This paper proposes a novel approach of a multiobjective mathematical model on team harmony and player performance. Two objectives are chosen as these are the most important perspectives that define the best team. The model outputs are nondominated solutions of these two objectives. Findings These solutions are displayed to the team coach to decide the best team according to strategical, psychological and conditional preferences of him/her. A real-life example is demonstrated to show the model validity and interpretation of the results by using the technique for order preference by similarity to an ideal solution on a volleyball team formation problem. Originality/value This paper proposes a multiobjective mathematical model on team harmony and player performance to solve the team coach's hard and complicated problem.
New formulations for multiple traveler minimum latency problem with time windows
(2022) Uzun, Gozde Onder; Kara, Imdat; ABH-1078-2021
In this paper, new mathematical models for homogeneous and heterogeneous multiple traveler minimum latency problem with time windows (kLPTW), named as M2 and M4 are developed. These models are computationally compared with existing models named as M1 and M3 for kLPTW in terms of CPU times and percentage deviation from linear programming relaxation values. A short summary of the computational analysis is given in table A below. In Table A, k is the number of travelers. The first column under the number of traveler cell shows the average CPU times of problems solved in time limit and the second column shows the average percentage deviations. We observed that, our formulations are superior than the existing formulations for all the problems for both kLPTW types with respect to each performance criteria. Purpose: The aim of this study is to develop new mathematical formulations for homogeneous and heterogeneous multiple traveler minimum latency problem with time windows. Theory and Methods: Based on the mixed integer linear programming, mathematical models with polynomial number of decision variables and constraints are developed. Benchmark instances from the literature are solved with existing formulations and proposed new formulations by using CPLEX 12.5.0.1. CPU times and percentage deviation from linear programming relaxation values are considered as performance criteria. Results: We solved 125 problems with varying number of nodes and time windows. In all the problem solved proposed formulations are better than the existing formulations in terms of both of the performance criteria. Conclusion: The proposed formulations for homogeneous and heterogeneous multiple traveler minimum latency problem with time windows are superior than the existing formulations and able to solve the problems up to 100 nodes with narrow time windows. Proposed formulations may be used to solve small and moderate real-life problems very easily. They may also be used for testing the performance of the heuristics constructed for kLPTW.
New Formulations for the Orienteering Problem
(2016) Kara, Imdat; Bicakci, Papatya Sevgin; Derya, Tusan; ABH-1078-2021
Problems associated with determining optimal routes from one or several depots (origin, home city) to a set of nodes (vertices, cities, customers, locations) are known as routing problems. The Traveling Salesman Problem (TSP) lies at the heart of routing problems. One of the new variants of the TSP is named as TSP with Profits where the traveler must finish its journey within a predetermined time (cost, distance), by optimizing given objective. In this variant of TSP, all cities ought to not to be visited. The Orienteering Problem (OP) is the most studied case of TSP with Profits which comes from an outdoor sport played on mountains. In OP, traveler gets a gain (profit, reward) from the visited node and the objective is to maximize the total gain that the traveler collects during the predetermined time. The OP is also named as selective TSP. In this paper, we present two polynomial size formulations for OP. The performance of our proposed formulations is tested on benchmark instances. We solved the benchmark problems from the literature via CPLEX 12.5 by using the proposed formulations and existing formulation. The computational experiments demonstrate that; (1) both of the new formulations over estimates the existing one; and (2) the proposed formulations are capable of solving all the benchmark instances that were solved by using special heuristics so far. (C) 2016 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license
New Formulations for The Traveling Repairman Problem with Time Windows
(2018) Kara, Imdat; Uzun, Gozde Onder; ABH-1078-2021
New formulations for the traveling repairman problem with time windows
(2021) Uzun, Gozde Onder; Kara, Imdat; ABH-1078-2021
The Traveling Repairman Problem (TRP) is one of the most important variants of the Traveling Salesman Problem (TSP). The objective function of TRP is to find a Hamiltonian path or tour starting from the origin while minimizing the total latency (waiting or delay time) for all customers. The latency of a customer is defined as the time passed from the beginning of a tour (or path) until a customer?s service is completed. TRP with time windows (TRPTW) is the case where the earliest and latest times for visiting each customer are restricted by prescribed time windows. The literature on TRPTW is scarce. We only found one formulation for TRPTW and one formulation for its variant. In this paper, we propose four new mathematical models for TRPTW with O(n2) binary variables and O(n2) constraints. We computationally analyze the performance of existing and new formulations by solving symmetric and asymmetric benchmark instances with CPLEX 12.5.0.1 and compare the results in terms of CPU times and optimality gap. We observed that our two formulations were extremely faster than existing formulations, and they could optimally solve symmetric instances up to 150 nodes and asymmetric instances up to 131 nodes within seconds.
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-2021
The 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.
New integer programming formulation for multiple traveling repairmen problem
(2017) Onder, Gozde; Kara, Imdat; Derya, Tusan; ABH-1078-2021
The multiple traveling repairman problem (kTRP) is a generalization of the traveling repairman problem which is also known as the minimum latency problem and the deliveryman problem. In these problems, waiting time or latency of a customer is defined as the time passed from the beginning of the travel until this customer's service completed. The objective is to find a Hamiltonian Tour or a Hamiltonian Path that minimizes the total waiting time of customers so that each customer is visited by one of the repairmen. In this paper, we propose a new mixed integer linear programming formulation for the multiple traveling repairman problem where each repairman starts from the depot and finishes the journey at a given node. In order to see the performance of the proposed formulation against existing formulations, we conduct computational analysis by solving benchmark instances appeared in the literature. Computational results show that proposed model is extremely effective than the others in terms of CPU times. (C) 2016 The Authors. Published by Elsevier
Order Acceptance and Scheduling Problem: A Proposed Formulation and the Comparison with the Literature
(2020) Bicakci, Papatya S.; Kara, Imdat
In classical scheduling problem, it is assumed that all orders must be processed. In the order acceptance and scheduling (OAS) problem, some orders are rejected due to limited capacity. In make-to-order production environment, in which the OAS problem occurs, accepting all orders may cause overloads, delay in deliveries and unsatisfied customers. Oguz et al. (2010) introduced the OAS problem with sequence-dependent setup times and release dates. In this paper, we propose a new mixed integer programming formulation with O(n(2)) decision variables and O(n2) constraints for the same problem. We conduct a computational analysis comparing the performance of our formulation with Oguz et al. (2010) formulation. We use the benchmark instances, which are available in the literature. We observe that our formulation can solve all the instances up to 50 orders in a reasonable time, while Oguz et al. (2010) formulation can solve only the instances with 10 orders in the same time limit.
Single-Machine Order Acceptance and Scheduling Problem Considering Setup Time and Release Date Relations
(2020) Bicakci, Papatya S.; Kara, Imdat; Sagir, Mujgan
This paper focuses on a make-to-order production system, where rejection of some orders is inevitable due to limited production capacity. In such a system, accepting all orders may cause overloads, order delays, and customer dissatisfaction. For this reason, firms tend to reject some orders. The order acceptance and scheduling problem is defined as deciding simultaneously which orders to be selected and how to schedule these selected orders. An extension of this problem with sequence-dependent setup times and release dates has been rarely studied, and the existing studies suggest that setup activities wait for the release date to be performed. However, in real production environments this may not be the case. Therefore, this paper examines the relationships between setup times and release dates considering the overall scheduling literature. Previous scheduling studies define two different relationships concerning setup times and release dates. One of them considers setup time is completely dependent on release date, and the other one claims that they are completely independent. In this paper, a new relationship is addressed to propound that setup time may be partially dependent on the release date. The paper also proposes a new mixed integer linear programming formulation withO(n(2)) binary decision variables andO(n(2)) constraints. It includes a detailed computational analysis by solving available instances in the literature, which suggests that existing formulation can solve the test problems to optimality with up to 10 orders in a given time limit. Our proposed formulation, however, can solve the test problems to optimality with up to 50 orders within the same time limit. According to the findings, our approach seems to be more suitable for real-life applications, and the proposed formulation is extremely faster than the existing one.
Single-Machine Order Acceptance and Scheduling Problem Considering Setup Time and Release Date Relations (vol 46, pg 1549, 2021)
(2021) Bicakci, Papatya S.; Kara, Imdat; Sagir, Mujgan; ABH-1078-2021
Solution Approaches for the Parallel Machine Order Acceptance and Scheduling Problem with Sequence-Dependent Setup Times, Release Dates and Deadliness
(2021) Bicakc, Papatya S.; Derya, Tusan; Kara, Imdat; ABH-1078-2021
Order acceptance and scheduling problem arises when there is limited capacity to process all orders in a make-to-order environment. The paper examines the identical parallel machines order acceptance and scheduling problem with sequence-dependent setup times, release dates and deadlines. The extant literature is deeply researched, and it is concluded that well-designed mathematical formulations are still necessitated in this area. Therefore, a new formulation is proposed for this problem and a recent formulation is chosen from the literature in order to make the comparison. An extensive computational analysis is conducted to test the performance of the formulations. The proposed formulation outperformed the existing one in terms of run times and the number of optimal values. Besides, a variable neighbourhood search-based simulated annealing algorithm is propounded to solve large-sized instances. As a result, it is observed that the heuristic algorithm can solve large-sized instances effectively in a very short span of time.
A Systematic Approach to Reduce Human and System-related Errors Causing Customer Dissatisfaction in a Production Environment
(2009) Pakdil, Fatma; Oezkoek, Onur; Dengiz, Berna; Kara, Imdat; Selvi, Nilay; Karg, Alper; ABH-1078-2021
In this study, a systematic methodology for business process improvement, which aims to eliminate human and system-related errors resulting in customer dissatisfaction in a production environment, is presented. The proposed methodology consists of problem identification and analysis, preventing human-related errors and system-related error steps respectively. The methodology was also implemented in a real-life organisation. Current and proposed systems are compared via a simulation model to examine the results of process improvements. The case study shows that the proposed methodology works exceedingly well and yields considerable improvement in the process under study. The most important and impressive difference of this paper from the previous literature is that process improvement needs are derived directly from customer dissatisfaction reasons and solved by the proposed systematic methodology. In this way human-related and system-related errors were perceived opportunities for improvement.
Traveling Repairmen Problem: A Biogeography-Based Optimization
(2022) Uzun, Gozde Onder; Dengiz, Berna; Kara, Imdat; Karasan, Oya Ekin
Traveling Repairman Problem (TRP), which is also known by names cumulative traveling salesman problem, the deliveryman problem and the minimum latency problem, is a special variant of Traveling Salesman Problem (TSP). In contrast to the minimization of completion time objective of TSP, the desired objective of TRP is to minimize the cumulative latency (waiting time or delay time) of all customers. In this paper, a generalized version of TRP with multi depots and time windows, namely Multi Depot Traveling Repairman Problem with Time Windows (MDTRPTW) is considered. A group of homogeneous repairmen initiate and finish their visit tours at multiple depots. Each customer must be visited exactly by one repairman within their provided earliest end latest times. Being a challenging Nondeterministic Polynomial-hard (NP-hard) optimization problem, exact solution approaches are not expected to scale to realistic dimensions of MDTRPTW. Thus, we propose a biogeography-based optimization algorithm (BBOA) as a metaheuristic approach to solve large size MDTRPTW problems. The proposed metaheuristic is analyzed in terms of solution quality, coefficient of variation as well as computation time by solving some test problems adapted from the related literature. The efficacy of the proposed solution methodology is demonstrated by solving instances with 288 customers within seconds.