Montréal, Canada
Montréal, Canada
Time filter
Source Type

Lahrichi N.,CIRRELT | Lahrichi N.,Ecole Polytechnique de Montréal | Crainic T.G.,CIRRELT | Gendreau M.,CIRRELT | And 4 more authors.
Journal of the Operational Research Society | Year: 2015

The dairy transportation problem (DTP) consists of determining the best routes to be performed for collecting milk from farms and delivering it to processing plants. We study the particular case of the province of Quebec, where the Fédération des producteurs de lait du Québec is responsible for negotiating the transportation costs on behalf of producers. Several issues are highlighted in the actual process of designing contracts such as using historical data. We propose an approach based on scenario analysis that consists of revising both the steps and the information used to construct the routes. We develop a generalized tabu search algorithm that integrates the different characteristics of the DTP. © 2015 Operational Research Society Ltd. All rights reserved.

Hajji A.,Laval University | Gharbi A.,CIRRELT | Artiba A.,University of Valenciennes and Hainaut‑Cambresis
2011 4th International Conference on Logistics, LOGISTIQUA'2011 | Year: 2011

This paper considers a stochastic optimal control problem of unreliable three stages manufacturing systems. The supplier and the transformation stage are both subject to random events. Moreover, due to the periods of unavailability of the supplier, a random delay could postpone the reception of the order. Our objective is to find a control policy for the supply and production activities that minimizes the incurred cost and to propose a practical approach aiming to evaluate and quantify the control policy. Stochastic dynamic programming and numerical methods combined to a simulation based approach are thus proposed to achieve a close approximation of the production and supply policy. To illustrate the usefulness of the combined approach extensions to cover more complex systems, were optimal control theory may not be easily used, are developed and analyzed. To illustrate the practical usefulness of the approach, an application aiming to develop a quantitative tool to help establishing and negotiating order costs is presented. © 2011 IEEE.

Rancourt M.-E.,CIRRELT | Bellavance F.,HEC Montréal | Goentzel J.,Massachusetts Institute of Technology
Socio-Economic Planning Sciences | Year: 2014

Empirical research characterizing transportation markets in developing countries is scarce. By analyzing contracts between the World Food Programme and private carriers, we identify the determinants of transportation tariffs in Ethiopia and quantify their relative importance. The econometric models devised from our unique dataset provide insights for shippers to improve procurement processes, for carriers to develop competitive business models and for government authorities to define effective investments and policies. Results indicate that the number of carriers on a given lane significantly reduces transportation tariffs and that policies stimulating competition may be as important as road infrastructure investments in Ethiopia's development strategy. © 2014 Elsevier Ltd.

Vidal T.,Pontifical Catholic University of Rio de Janeiro | Crainic T.G.,CIRRELT | Gendreau M.,Ecole Polytechnique de Montréal | Prins C.,University of Technology of Troyes
Networks | Year: 2015

Timing problems involve the choice of task execution dates within a predetermined processing sequence, and under various additional constraints or objectives such as time windows, time-dependent costs, or flexible processing times, among others. Their efficient resolution is critical in branch and bound and neighborhood search methods for vehicle routing, project and machine scheduling, as well as in various applications in network optimization, resource allocation, and statistical inference. Timing-related problems have been studied for years, yet research on this subject suffers from a lack of consensus, and most knowledge is scattered among operations research and applied mathematics domains. This article introduces a classification of timing problems and features, as well as a unifying multidisciplinary analysis of timing algorithms. In relation to frequent application cases within branching schemes or neighborhood searches, the efficient resolution of series of similar timing subproblems is also analyzed. A dedicated formalism of reoptimization "by concatenation" is introduced to that extent. The knowledge developed through this analysis is valuable for modeling and algorithmic design, for a wide range of combinatorial optimization problems with time characteristics, including rich vehicle routing settings and emerging nonregular scheduling applications, among others. © 2015 Wiley Periodicals, Inc.

Crainic T.G.,CIRRELT | Perboli G.,Polytechnic University of Turin | Rei W.,CIRRELT | Tadei R.,Polytechnic University of Turin
Computers and Operations Research | Year: 2011

We consider the variable cost and size bin packing problem, a generalization of the well-known bin packing problem, where a set of items must be packed into a set of heterogeneous bins characterized by possibly different volumes and fixed selection costs. The objective of the problem is to select bins to pack all items at minimum total bin-selection cost. The paper introduces lower bounds and heuristics for the problem, the latter integrating lower and upper bound techniques. Extensive numerical tests conducted on instances with up to 1000 items show the effectiveness of these methods in terms of computational effort and solution quality. We also provide a systematic numerical analysis of the impact on solution quality of the bin selection costs and the correlations between these and the bin volumes. The results show that these correlations matter and that solution methods that are un-biased toward particular correlation values perform better. © 2011 Elsevier Ltd.

Perboli G.,Polytechnic University of Turin | Crainic T.G.,CIRRELT | Tadei R.,Polytechnic University of Turin
IEEE International Conference on Automation Science and Engineering | Year: 2011

In this paper, we introduce GASP - Greedy Adaptive Search Procedure, a metaheuristic able to efficiently address two and three-dimensional multiple container packing problems. GASP combines the simplicity of greedy algorithms with learning mechanisms aimed to guide the overall method towards good solutions. Extensive experiments indicate that GASP attains near-optimal solutions in very short computational times, and improves state-of-the-art results in comparable computational times. © 2011 IEEE.

Crainic T.G.,CIRRELT | Mancini S.,Polytechnic University of Turin | Perboli G.,Polytechnic University of Turin | Tadei R.,Polytechnic University of Turin
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011

In this paper we address the Two-Echelon Vehicle Routing Problem (2E-VRP), an extension of the classical Capacitated VRP, where the delivery from a single depot to the customers is managed by routing and consolidating the freight through intermediate depots called satellites. We present a family of Multi-Start heuristics based on separating the depot-to-satellite transfer and the satellite-to-customer delivery by iteratively solving the two resulting routing subproblems, while adjusting the satellite workloads that link them. The common scheme on which all the heuristics are based consists in, after having found an initial solution, applying a local search phase, followed by a diversification; if the new obtained solutions are feasible, then local search is applied again, otherwise a feasibility search procedure is applied, and if it successful, the local search is applied on the newfound solution. Different diversification strategies and feasibility search rules are proposed. We present computational results on a wide set of instances up to 50 customers and 5 satellites and compare them with results from the literature, showing how the new methods outperform previous existent methods, both in efficiency and accuracy. © 2011 Springer-Verlag.

Perboli G.,CIRRELT | Perboli G.,Polytechnic University of Turin | Rosano M.,Polytechnic University of Turin | Gobbato L.,Polytechnic University of Turin
ILS 2016 - 6th International Conference on Information Systems, Logistics and Supply Chain | Year: 2016

In recent years, freight transportation emerged as a key factor in the development and dynamicity of countries, although it has a considerably impact on urban areas, due to the environmental issues. In this context, several stakeholders have implemented City Logistics solutions in order to make transportation more sustainable and efficient. This paper proposes a case study concerning the collaborative transportation system involving traditional and green couriers, in the city of Turin. This freight pooling is supported by a decision support system that combines the ERP "Odoo" with an algorithm for the optimization planning of routes. This decision support system is described in the second section and finally, some results obtained from its application are discussed.

Crainic T.G.,CIRRELT | Hewitt M.,Loyola University Chicago | Rei W.,CIRRELT
Computers and Operations Research | Year: 2014

We propose a methodological approach to build strategies for grouping scenarios as defined by the type of scenario decomposition, type of grouping, and the measures specifying scenario similarity. We evaluate these strategies in the context of stochastic network design by analyzing the behavior and performance of a new progressive hedging-based meta-heuristic for stochastic network design that solves subproblems comprising multiple scenarios. We compare the proposed strategies not only among themselves, but also against the strategy of grouping scenarios randomly and the lower bound provided by a state-of-the-art MIP solver. The results show that, by solving multi-scenario subproblems generated by the strategies we propose, the meta-heuristic produces better results in terms of solution quality and computing efficiency than when either single-scenario subproblems or multiple-scenario subproblems that are generated by picking scenarios at random are solved. The results also show that, considering all the strategies tested, the covering strategy with respect to commodity demands leads to the highest quality solutions and the quickest convergence. © 2013 Elsevier Ltd.

Vidal T.,University of Technology of Troyes | Vidal T.,University of Montréal | Crainic T.G.,CIRRELT | Gendreau M.,Ecole Polytechnique de Montréal | Prins C.,University of Technology of Troyes
Computers and Operations Research | Year: 2013

The paper presents an efficient Hybrid Genetic Search with Advanced Diversity Control for a large class of time-constrained vehicle routing problems, introducing several new features to manage the temporal dimension. New move evaluation techniques are proposed, accounting for penalized infeasible solutions with respect to time-window and duration constraints, and allowing to evaluate moves from any classical neighbourhood based on arc or node exchanges in amortized constant time. Furthermore, geometric and structural problem decompositions are developed to address efficiently large problems. The proposed algorithm outperforms all current state-of-the-art approaches on classical literature benchmark instances for any combination of periodic, multi-depot, site-dependent, and duration-constrained vehicle routing problem with time windows. © 2012 Elsevier Ltd. All rights reserved.

Loading CIRRELT collaborators
Loading CIRRELT collaborators