https://hal-utt.archives-ouvertes.fr/hal-02491608Mingozzi, AristideAristideMingozziUNIBO - Alma Mater Studiorum Università di Bologna [Bologna]Prins, ChristianChristianPrinsLOSI - Laboratoire d'Optimisation des Systèmes Industriels - ICD - Institut Charles Delaunay - UTT - Université de Technologie de Troyes - CNRS - Centre National de la Recherche ScientifiqueWolfler Calvo, RobertoRobertoWolfler CalvoLOSI - Laboratoire d'Optimisation des Systèmes Industriels - ICD - Institut Charles Delaunay - UTT - Université de Technologie de Troyes - CNRS - Centre National de la Recherche ScientifiqueCapacitated Depot Location for the Vehicle Routing ProblemHAL CCSD2006VehiclesRoutingPaper technologyStochastic processesTraveling salesman problemsPartitioning algorithmsLagrangian functionsInteger linear programmingCost functionUpper boundlocation routingadditive boundingcolumns generation[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]Gavrysiak, Daniel2020-02-26 11:39:092022-06-26 01:38:392020-02-26 11:39:09enConference papers10.1109/ICSSSM.2006.3207661In this working paper we consider the problem of opening one or more depots on a given set of a priori defined depot locations and to design for each opened depot a number of routes in order to supply a given set of customers. With each location is associated a fixed cost for opening a depot and a depot-capacity that limits the quantity that can be delivered to customers. All vehicles are identical. Each route must start and finish at the same depot. The route cost is equal to the distance traveled. The objective is to minimize the sum of the fixed costs of the opened depots and of the costs of the routes operated by the depots. We describe a lower bound and the framework of an exact method that is based on a set partitioning (SP) like formulation of the problem that is a generalization of the SP formulation of the capacitated vehicle routing problem and of the multi-depot capacitated vehicle routing problem