Araştırma Çıktıları | TR-Dizin | WoS | Scopus | PubMed
Permanent URI for this communityhttps://hdl.handle.net/11727/4806
Browse
12 results
Search Results
Item Traveling Repairmen Problem: A Biogeography-Based Optimization(2022) Uzun, Gozde Onder; Dengiz, Berna; Kara, Imdat; Karasan, Oya EkinTraveling 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.Item New formulations for multiple traveler minimum latency problem with time windows(2022) Uzun, Gozde Onder; Kara, Imdat; ABH-1078-2021In 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.Item A multiobjective mathematical model to form the best team at sports clubs: team harmony and player performance objectives(2022) Budak, Gercek; Kara, ImdatPurpose 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.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.Item 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-2021Order 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.Item New formulations for the traveling repairman problem with time windows(2021) Uzun, Gozde Onder; Kara, Imdat; ABH-1078-2021The 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.Item 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-2021Item Order Acceptance and Scheduling Problem: A Proposed Formulation and the Comparison with the Literature(2020) Bicakci, Papatya S.; Kara, ImdatIn 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.Item Single-Machine Order Acceptance and Scheduling Problem Considering Setup Time and Release Date Relations(2020) Bicakci, Papatya S.; Kara, Imdat; Sagir, MujganThis 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.Item Formulations for Minimizing Tour Duration of the Traveling Salesman Problem with Time Windows(2015) Kara, Imdat; Derya, Tusan; ABH-1078-2021Traveling 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.