Browsing by Author "Laporte, G."

Now showing 1 - 8 of 8

Metadata only
The attractive traveling salesman problem
(Elsevier, 2010-05-16) Erdoğan, Güneş; Cordeau, J.-F.; Laporte, G.; Industrial Engineering; ERDOĞAN, Güneş
In the Attractive Traveling Salesman Problem the vertex set is partitioned into facility vertices and customer vertices. A maximum profit tour must be constructed on a subset of the facility vertices. Profit is computed through an attraction function: every visited facility vertex attracts a portion of the profit from the customer vertices based on the distance between the facility and customer vertices, and the attractiveness of the facility vertex. A gravity model is used for computing the profit attraction. The problem is formulated as an integer non-linear program. A linearization is proposed and strengthened through the introduction of valid inequalities, and a branch-and-cut algorithm is developed. A tabu search algorithm is also implemented. Computational results are reported.
Metadata only
A branch-and-cut algorithm for solving the non-preemptive capacitated swapping problem
(Elsevier, 2010-08-06) Erdoğan, Güneş; Cordeau, J.-F.; Laporte, G.; Industrial Engineering; ERDOĞAN, Güneş
This paper models and solves a capacitated version of the Non-Preemptive Swapping Problem. This problem is defined on a complete digraph , at every vertex of which there may be one unit of supply of an item, one unit of demand, or both. The objective is to determine a minimum cost capacitated vehicle route for transporting the items in such a way that all demands are satisfied. The vehicle can carry more than one item at a time. Three mathematical programming formulations of the problem are provided. Several classes of valid inequalities are derived and incorporated within abranch-and-cut algorithm, and extensive computational experiments are performed on instances adapted from TSPLIB.
Metadata only
Collaborative prepositioning network design for regional disaster response
(Wiley, 2019-10) Koyuncu, Burcu Balçık; Silvestri, S.; Rancourt, M.‐È.; Laporte, G.; Industrial Engineering; KOYUNCU, Burcu Balçık
We present a collaborative prepositioning strategy to strengthen the disaster preparedness of the Caribbean countries, which are frequently hit by hurricanes. Since different subsets of countries are affected in each hurricane season, significant risk pooling benefits can be achieved through horizontal collaboration, which involves joint ownership of prepositioned stocks. We worked with the intergovernmental Caribbean Disaster and Emergency Management Agency to design a collaborative prepositioning network in order to improve regional response capacity. We propose a novel insurance-based method to allocate the costs incurred to establish and operate the proposed collaborative prepositioning network among the partner countries. We present a stochastic programming model, which determines the locations and amounts of relief supplies to store, as well as the investment to be made by each country such that their premium is related to the cost associated with the expected value and the standard deviation of their demand. We develop a realistic data set for the network by processing real-world data. We conduct extensive numerical analyses and present insights that support practical implementation. We show that a significant reduction in total inventory can be achieved by applying collaborative prepositioning as opposed to a decentralized policy. Our results also demonstrate that reducing the replenishment lead time during the hurricane season and improving sea connectivity are essential to increasing the benefits resulting from the network.
Metadata only
A cost-sharing mechanism for multi-country partnerships in disaster preparedness
(Wiley, 2021-12) Rodríguez-Pereira, J.; Koyuncu, Burcu Balçık; Rancourt, M.-E.; Laporte, G.; Industrial Engineering; KOYUNCU, Burcu Balçık
We study a multi-country disaster preparedness partnership involving the joint prepositioning of emergency relief items. Our focus is the Caribbean region, which faces increasing disaster threats due to weather-related events and has committed to share its resources for regional integration. We collaborate with the inter-governmental Caribbean Disaster and Emergency Management Agency (CDEMA), which is interested in creating a methodology to equitably (fairly) allocate the costs necessary to operationalize this commitment. We present alternative cost allocation methods among the partner countries by considering their risk level and their ability to pay. Specifically, we adapt some techniques such as the Shapley value, the equal profit method, and the alternative cost avoided method, and we also propose a new insurance-based allocation scheme to determine the country contributions. This mechanism, which is formulated as a linear programming model, sets country premiums by considering the expected value and the standard deviation of country demands and their gross national income. We discuss the structural properties of these methods and numerically evaluate their performance in achieving an equitable allocation scheme with respect to three equity indicators based on the Gini coefficient. Our proposed cost-sharing mechanism not only achieves superior solutions compared with other methodologies with respect to the proposed equity metrics, but is also computationally efficient. We numerically illustrate how it can be used to obtain alternative cost allocation plans by giving different weights to disaster risk and economic standing parameters, and we analyze the benefits and fairness of the partnership in a transparent way.
Metadata only
Designing new electoral districts for the city of Edmonton
(Informs, 2011-12-11) Bozkaya, B.; Erkut, Erhan; Haight, D.; Laporte, G.; Business Administration; ERKUT, Erhan
Every few years, the city of Edmonton, Canada must review and evaluate changes to its electoral district boundaries. The review process that was completed in 2009 resulted in modifying the district plan from a six-ward system with two council members in each to a single-member 12-ward system. The authors of this paper designed the redistricting plan. This paper describes the algorithm we applied to solve the problem and the decision support system we used. The algorithm is based on a multicriteria mathematical model, which is solved by a tabu search heuristic embedded within a geographic information system (GIS)-based decision support system. The resulting district plan meets districting criteria, including population balance, contiguity, compactness, respect for natural boundaries, growth areas, and integrity of communities of interest. This plan was formally approved as a city bylaw and used in the municipal elections in 2010.
Metadata only
Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs
(Elsevier, 2012-05) Erdoğan, Güneş; Battarra, M.; Laporte, G.; Vigo, D.; Industrial Engineering; ERDOĞAN, Güneş
This paper studies the Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs. The subproblem of minimizing the handling cost for a fixed route is analyzed in detail. It is solved by means of an exact dynamic programming algorithm with quadratic complexity and by an approximate linear time algorithm. Three metaheuristics integrating these solution methods are developed. These are based on tabu search, iterated local search and iterated tabu search. The three heuristics are tested and compared on instances adapted from the related literature. The results show that the combination of tabu search and exact dynamic programming performs the best, but using the approximate linear time algorithm considerably decreases the CPU time at the cost of slightly worse solutions.
Open Access
Scheduling ambulance crews for maximum coverage
(Palgrave MacMillan, 2010-04) Erdoğan, Güneş; Erkut, Erhan; Ingolfsson, A.; Laporte, G.; Business Administration; Industrial Engineering; ERDOĞAN, Güneş; ERKUT, Erhan
This paper addresses the problem of scheduling ambulance crews in order to maximize the coverage throughout a planning horizon. The problem includes the subproblem of locating ambulances to maximize expected coverage with probabilistic response times, for which a tabu search algorithm is developed. The proposed tabu search algorithm is empirically shown to outperform previous approaches for this subproblem. Two integer programming models that use the output of the tabu search algorithm are constructed for the main problem. Computational experiments with real data are conducted. A comparison of the results of the models is presented.
Metadata only
The traveling salesman problem with pickups, deliveries, and handling costs
(Informs, 2010-08) Battarra, M.; Erdoğan, Güneş; Laporte, G.; Vigo, D.; Industrial Engineering; ERDOĞAN, Güneş
This paper introduces a new variant of the one-to-many-to-one single vehicle pickup and delivery problems (SVPDP) that incorporates the handling cost incurred when rearranging the load at the customer locations. The simultaneous optimization of routing and handling costs is difficult, and the resulting loading patterns are hard to implement in practice. However, this option makes economical sense in contexts where the routing cost dominates the handling cost. We have proposed some simplified policies applicable to such contexts. The first is a two-phase heuristic in which the tour having minimum routing cost is initially determined by optimally solving an SVPDP, and the optimal handling policy is then determined for that tour. In addition, branch-and-cutalgorithms based on integer linear programming formulations are proposed, in which routing and handling decisions are simultaneously optimized, but the handling decisions are restricted to three simplified policies. The formulations are strengthened by means of problem specific valid inequalities. The proposed methods have been extensively tested on instances involving up to 25 customers and hundreds of items. Our results show the impact of the handling aspect on the customer sequencing and indicate that the simplified handling policies favorably compare with the optimal one.