Mühendislik Fakültesi / Faculty of Engineering

Permanent URI for this collectionhttps://hdl.handle.net/11727/1401

Browse

Filters

2015 - 201932020 - 20224

Settings

Author: search.filters.author.Kara, ImdatHas files: Yes

Search Results

Now showing 1 - 7 of 7
  • No Thumbnail Available
    Item
    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.
  • No Thumbnail Available
    Item
    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.
  • No Thumbnail Available
    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-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.
  • No Thumbnail Available
    Item
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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
  • Thumbnail Image
    Item
    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