Mühendislik Fakültesi / Faculty of Engineering

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

Browse

Filters

2021 - 20222

Settings

search.filters.applied.f.rights: search.filters.rights.info:eu-repo/semantics/closedAccessSubject: search.filters.subject.Routing

Search Results

Now showing 1 - 2 of 2
  • 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 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.