Mühendislik Fakültesi / Faculty of Engineering
Permanent URI for this collectionhttps://hdl.handle.net/11727/1401
Browse
5 results
Search Results
Item Selective generalized travelling salesman problem(2020) Derya, Tusan; Dinler, Esra; Kececi, Baris; 0000-0002-2730-5993; F-1639-2011This paper introduces the Selective Generalized Traveling Salesman Problem (SGTSP). In SGTSP, the goal is to determine the maximum profitable tour within the given threshold of the tour's duration, which consists of a subset of clusters and a subset of nodes in each cluster visited on the tour. This problem is a combination of cluster and node selection and determining the shortest path between the selected nodes. We propose eight mixed integer programming (MIP) formulations for SGTSP. All of the given MIP formulations are completely new, which is one of the major novelties of the study. The performance of the proposed formulations is evaluated on a set of test instances by conducting 4608 experimental runs. Overall, 4138 out of 4608 (similar to 90%) test instances were solved optimally by using all formulations.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.Item New Formulations for the Orienteering Problem(2016) Kara, Imdat; Bicakci, Papatya Sevgin; Derya, Tusan; ABH-1078-2021Problems 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 licenseItem New integer programming formulation for multiple traveling repairmen problem(2017) Onder, Gozde; Kara, Imdat; Derya, Tusan; ABH-1078-2021The 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 ElsevierItem A COMPARATIVE STUDY OF THE CAPABILITY OF ALTERNATIVE MIXED INTEGER PROGRAMMING FORMULATIONS(2018) Keseci, Baris; Derya, Tusan; Dinler, Esra; Ic, Yusuf Tansel; AAC-4793-2019; F-1639-2011; AAI-1081-2020In selecting the best mixed integer linear programming (MILP) formulation the important issue is to figure out how to evaluate the performance of each candidate formulation in terms of selected criteria. The main objective of this study is to propose a systematic approach to guide the selection of the best MILP formulation among the alternatives according to the needs of the decision maker. For this reason we consider the problem of "selecting the most appropriate MILP formulation for a certain type of decision maker" as a multi-criteria decision making problem and present an integrated AHP-TOPSIS decision making methodology to select the most appropriate formulation. As an example the proposed decision making methodology is implemented on the selection of the MILP formulations of the Capacitated Vehicle Routing Problem (CVRP). A numerical example is provided for illustrative purposes. As a result, the proposed decision model can be a tool for the decision makers (here they are the scientists, engineers and practitioners) who intend to choose the appropriate mathematical model(s) among the alternatives according to their needs on their studies. The integrated AHP-TOPSIS approach can simply be incorporated into a computer-based decision support system since it has simplicity in both computation and application.