Multi-Objective Genetic Algorithms for the Single Allocation Hub Location Problem

Hub Location Problems play vital economic roles in transportation and telecommunication networks where goods or people must be efficiently transferred from an origin to a destination point whilst direct origin-destination links are impractical. This work investigates the single allocation hub location problem, and proposes a genetic algorithm (GA) approach for it. The effectiveness of using a single-objective criterion measure for the problem is first explored. Next, a multi-objective GA employing various fitness evaluation strategies such as Pareto ranking, sum of ranks, and weighted sum strategies is presented. The effectiveness of the multi-objective GA is shown by comparison with an Integer Programming strategy, the only other multi-objective approach found in the literature for this problem. Lastly, two new crossover operators are proposed and an empirical study is done using small to large problem instances of the Civil Aeronautics Board (CAB) and Australian Post (AP) data sets.

Scheduled service network design for integrated planning of rail freight transportation

Cette thèse étudie une approche intégrant la gestion de l’horaire et la conception de réseaux de services pour le transport ferroviaire de marchandises. Le transport par rail s’articule autour d’une structure à deux niveaux de consolidation où l’affectation des wagons aux blocs ainsi que des blocs aux services représentent des décisions qui complexifient grandement la gestion des opérations. Dans cette thèse, les deux processus de consolidation ainsi que l’horaire d’exploitation sont étudiés simultanément. La résolution de ce problème permet d’identifier un plan d’exploitation rentable comprenant les politiques de blocage, le routage et l’horaire des trains, de même que l’habillage ainsi que l’affectation du traffic. Afin de décrire les différentes activités ferroviaires au niveau tactique, nous étendons le réseau physique et construisons une structure de réseau espace-temps comprenant trois couches dans lequel la dimension liée au temps prend en considération les impacts temporels sur les opérations. De plus, les opérations relatives aux trains, blocs et wagons sont décrites par différentes couches. Sur la base de cette structure de réseau, nous modélisons ce problème de planification ferroviaire comme un problème de conception de réseaux de services. Le modèle proposé se formule comme un programme mathématique en variables mixtes. Ce dernie r s’avère très difficile à résoudre en raison de la grande taille des instances traitées et de sa complexité intrinsèque. Trois versions sont étudiées : le modèle simplifié (comprenant des services directs uniquement), le modèle complet (comprenant des services directs et multi-arrêts), ainsi qu’un modèle complet à très grande échelle. Plusieurs heuristiques sont développées afin d’obtenir de bonnes solutions en des temps de calcul raisonnables. Premièrement, un cas particulier avec services directs est analysé. En considérant une cara ctéristique spécifique du problème de conception de réseaux de services directs nous développons un nouvel algorithme de recherche avec tabous. Un voisinage par cycles est privilégié à cet effet. Celui-ci est basé sur la distribution du flot circulant sur les blocs selon les cycles issus du réseau résiduel. Un algorithme basé sur l’ajustement de pente est développé pour le modèle complet, et nous proposons une nouvelle méthode, appelée recherche ellipsoidale, permettant d’améliorer davantage la qualité de la solution. La recherche ellipsoidale combine les bonnes solutions admissibles générées par l’algorithme d’ajustement de pente, et regroupe les caractéristiques des bonnes solutions afin de créer un problème élite qui est résolu de facon exacte à l’aide d’un logiciel commercial. L’heuristique tire donc avantage de la vitesse de convergence de l’algorithme d’ajustement de pente et de la qualité de solution de la recherche ellipsoidale. Les tests numériques illustrent l’efficacité de l’heuristique proposée. En outre, l’algorithme représente une alternative intéressante afin de résoudre le problème simplifié. Enfin, nous étudions le modèle complet à très grande échelle. Une heuristique hybride est développée en intégrant les idées de l’algorithme précédemment décrit et la génération de colonnes. Nous proposons une nouvelle procédure d’ajustement de pente où, par rapport à l’ancienne, seule l’approximation des couts liés aux services est considérée. La nouvelle approche d’ajustement de pente sépare ainsi les décisions associées aux blocs et aux services afin de fournir une décomposition naturelle du problème. Les résultats numériques obtenus montrent que l’algorithme est en mesure d’identifier des solutions de qualité dans un contexte visant la résolution d’instances réelles.

A heuristic algorithm for the Capacitated Vehicle Routing Problem with Synchronized Pick-ups and Drop-offs : a case study for medications delivery and supervision in DR Congo

Dans des contextes de post-urgence tels que le vit la partie occidentale de la République Démocratique du Congo (RDC), l’un des défis cruciaux auxquels font face les hôpitaux ruraux est de maintenir un niveau de médicaments essentiels dans la pharmacie. Sans ces médicaments pour traiter les maladies graves, l’impact sur la santé de la population est significatif. Les hôpitaux encourent également des pertes financières dues à la péremption lorsque trop de médicaments sont commandés. De plus, les coûts du transport des médicaments ainsi que du superviseur sont très élevés pour les hôpitaux isolés ; les coûts du transport peuvent à eux seuls dépasser ceux des médicaments. En utilisant la province du Bandundu, RDC pour une étude de cas, notre recherche tente de déterminer la faisabilité (en termes et de la complexité du problème et des économies potentielles) d’un problème de routage synchronisé pour la livraison de médicaments et pour les visites de supervision. Nous proposons une formulation du problème de tournées de véhicules avec capacité limitée qui gère plusieurs exigences nouvelles, soit la synchronisation des activités, la préséance et deux fréquences d’activités. Nous mettons en œuvre une heuristique « cluster first, route second » avec une base de données géospatiales qui permet de résoudre le problème. Nous présentons également un outil Internet qui permet de visualiser les solutions sur des cartes. Les résultats préliminaires de notre étude suggèrent qu’une solution synchronisée pourrait offrir la possibilité aux hôpitaux ruraux d’augmenter l’accessibilité des services médicaux aux populations rurales avec une augmentation modique du coût de transport actuel.

Optimal Methodology for Synchronized Scheduling of Parallel Station Assembly with Air Transportation

We present an optimal methodology for synchronized scheduling of production assembly with air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain (CESC). This problem was motivated by a major PC manufacturer in consumer electronics industry, where it is required to schedule the delivery requirements to meet the customer needs in different parts of South East Asia. The overall problem is decomposed into two sub-problems which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as a Linear Programming Problem with earliness tardiness penalties for job orders. For the assembly scheduling problem, it is basically required to sequence the job orders on the assembly stations to minimize their waiting times before they are shipped by flights to their destinations. Hence the second sub-problem is modelled as a scheduling problem with earliness penalties. The earliness penalties are assumed to be independent of the job orders.

The benefits of ethanol use for hydrogen production in urban transportation

The purpose of this paper is to describe the benefits of sugar cane ethanol in Brazil, appointing the productivity of this type of fuel based on hectares of plantation, its carbon dioxide cycle and the contribution to reduce the greenhouse effect. In the following step the uses of ethanol for hydrogen production by steam reforming is analyzed and some comparison with natural gas steam reforming is performed. The sugar cane industry in Brazil, in a near future, in the hydrogen era, could be modified according to our purpose, since besides the production of sugar, and ethylic and anhydric alcohol, Brazilian sugar cane industry will also be able to produce biohydrogen.Fuel cells appear like a promising technology for energy generation. Among several technologies in the present, the PEMFC (proton exchange membrane fuel cell) is the most appropriate for vehicles application, because it combines durability, high power density, high efficiency, good response and it works at relatively low temperatures. Besides that it is easy to turn it on and off and it is able to support present vibration in vehicles. A PEMFC's problem is the need of noble catalysts like platinum. Another problem is that CO needs to be in low concentration, requiring a more clean hydrogen to avoid fuel cell deterioration.One part of this paper was developed in Stockholm, where there are some buses within the CUTE (clean urban transport for Europe) project that has been in operation with FC since January 2004. Another part was developed in Guaratingueta, Brazil. Brazil intends to start up a program of FC buses. As conclusion, this paper shows the economical analysis comparing buses moved by fuel cells using hydrogen by different kinds of production. Electrolyze with wind turbine, natural gas steam reforming and ethanol steam reforming. (C) 2009 Elsevier Ltd. All rights reserved.

An approach using Lagrangian/surrogate relaxation for lot-sizing with transportation costs

Neste trabalho estuda-se um problema de dimensionamento de lotes e distribuição que envolve além de custos de estoques, produção e preparação, custos de transportes para o armazém da empresa. Os custos logísticos estão associados aos contêineres necessários para empacotar os produtos produzidos. A empresa negocia um contrato de longo prazo onde um custo fixo por período é associado ao transporte dos itens, em contrapartida um limite de contêineres é disponibilizado com custo mais baixo que o custo padrão. Caso ocorra um aumento ocasional de demanda, novos contêineres podem ser utilizados, no entanto, seu custo é mais elevado. Um modelo matemático foi proposto na literatura e resolvido utilizando uma heurística Lagrangiana. No presente trabalho a resolução do problema por uma heurística Lagrangiana/surrogate é avaliada. Além disso, é considerada uma extensão do modelo da literatura adicionando restrições de capacidade e permitindo atraso no atendimento a demanda. Testes computacionais mostraram que a heurística Lagrangiana/surrogate é competitiva especialmente quando se têm restrições de capacidade apertada.

On an Optimal Linear Control Applied to a Non-Ideal Load Transportation System, Modeled with Periodic Coefficients

In this paper, a load transportation system in platforms or suspended by cables is considered. It is a monorail device and is modelled as an inverted pendulum built on a car driven by a DC motor. The governing equations of motion were derived via Lagrange's equations. In the mathematical model we consider the interaction between the DC motor and the dynamical system, that is, we have a so-called non-ideal periodic problem. The problem is analysed and we also developed an optimal linear control design to stabilize the problem.

Nonlinear Dynamics and Control of an Ideal/Nonideal Load Transportation System With Periodic Coefficients

In this paper, a loads transportation system in platforms or suspended by cables is considered. It is a monorail device and is modeled as an inverted pendulum built on a car driven by a dc motor the governing equations of motion were derived via Lagrange's equations. In the mathematical model we consider the interaction between the dc motor and the dynamical system, that is, we have a so called nonideal periodic problem. The problem is analyzed, qualitatively, through the comparison of the stability diagrams, numerically obtained, for several motor torque constants. Furthermore, we also analyze the problem quantitatively using the Floquet multipliers technique. Finally, we devise a control for the studied nonideal problem. The method that was used for analysis and control of this nonideal periodic system is based on the Chebyshev polynomial exponsion, the Picard iterative method, and the Lyapunov-Floquet transformation (L-F transformation). We call it Sinha's theory.

Branch and bound algorithm for transmission system expansion planning using a transportation model

A method for optimal transmission network expansion planning is presented. The transmission network is modelled as a transportation network. The problem is solved using hierarchical Benders decomposition in which the problem is decomposed into master and slave subproblems. The master subproblem models the investment decisions and is solved using a branch-and-bound algorithm. The slave subproblem models the network operation and is solved using a specialised linear program. Several alternative implementations of the branch-and-bound algorithm have been rested. Special characteristics of the transmission expansion problem have been taken into consideration in these implementations. The methods have been tested on various test systems available in the literature.

Analysis of heuristic algorithms for the transportation model in static and multistage planning in network expansion systems

The usefulness of the application of heuristic algorithms in the transportation model, first proposed by Garver, is analysed in relation to planning for the expansion of transmission systems. The formulation of the mathematical model and the solution techniques proposed in the specialised literature are analysed in detail. Starting with the constructive heuristic algorithm proposed by Garver, an extension is made to the problem of multistage planning for transmission systems. The quality of the solutions found by heuristic algorithms for the transportation model is analysed, as are applications in problems of planning transmission systems.

Domain reduction using GRASP construction phase for transmission expansion planning problem

This paper proposes a new strategy to reduce the combinatorial search space of a mixed integer linear programming (MILP) problem. The construction phase of greedy randomized adaptive search procedure (GRASP-CP) is employed to reduce the domain of the integer variables of the transportation model of the transmission expansion planning (TM-TEP) problem. This problem is a MILP and very difficult to solve specially for large scale systems. The branch and bound (BB) algorithm is used to solve the problem in both full and the reduced search space. The proposed method might be useful to reduce the search space of those kinds of MILP problems that a fast heuristic algorithm is available for finding local optimal solutions. The obtained results using some real test systems show the efficiency of the proposed method. © 2012 Springer-Verlag.

PBL and B-Learning for Civil Engineering Students in a Transportation Course

The results of a pedagogical strategy implemented at the University of Sao Paulo at Sao Carlos are presented and discussed. The initiative was conducted in a transportation course offered to Civil Engineering students. The approach is a combination of problem-based learning and project-based learning (PBL) and blended-learning (B-learning). Starting in 2006, a different problem was introduced every year. From 2009 on, however, the problem-based learning concept was expanded to project-based learning. The performance of the students was analyzed using the following elements: (1) grades in course activities; (2) answers from a questionnaire designed for course evaluation; and (3) cognitive maps made to assess the effects of PBL through the comparison of the responses provided by the students involved and those not involved in the experiment. The results showed positive aspects of the method, such as a strong involvement of several students with the subject. A gradual increase in the average scores obtained by the students in the project activities (from 6.77 in 2006 to 8.24 in 2009) was concomitant with a better evaluation of these activities and of the course as a whole (90 and 97% of options "Good" or "Very good" in 2009, respectively). A growing interest in the field of transportation engineering as an alternative for further studies was also noticed. DOI: 10.1061/(ASCE)EI.1943-5541.0000115. (C) 2012 American Society of Civil Engineers.

Strategies and procedures for the development of intermodal freight transport in Europe: the role of motorways of the sea services and railway terminals

Since the birth of the European Union on 1957, the development of a single market through the integration of national freight transport networks has been one of the most important points in the European Union agenda. Increasingly congested motorways, rising oil prices and concerns about environment and climate change require the optimization of transport systems and transport processes. The best solution should be the intermodal transport, in which the most efficient transport options are used for the different legs of transport. This thesis examines the problem of defining innovative strategies and procedures for the sustainable development of intermodal freight transport in Europe. In particular, the role of maritime transport and railway transport in the intermodal chain are examined in depth, as these modes are recognized to be environmentally friendly and energy efficient. Maritime transport is the only mode that has kept pace with the fast growth in road transport, but it is necessary to promote the full exploitation of it by involving short sea shipping as an integrated service in the intermodal door-to-door supply chain and by improving port accessibility. The role of Motorways of the Sea services as part of the Trans-European Transport Network is is taken into account: a picture of the European policy and a state of the art of the Italian Motorways of the Sea system are reported. Afterwards, the focus shifts from line to node problems: the role of intermodal railway terminals in the transport chain is discussed. In particular, the last mile process is taken into account, as it is crucial in order to exploit the full capacity of an intermodal terminal. The difference between the present last mile planning models of Bologna Interporto and Verona Quadrante Europa is described and discussed. Finally, a new approach to railway intermodal terminal planning and management is introduced, by describing the case of "Terminal Gate" at Verona Quadrante Europa. Some proposals to favour the integrate management of "Terminal Gate" and the allocation of its capacity are drawn up.

GRASP with Hybrid Path Relinking for Bi-Objective Winner Determination in Combinatorial Transportation Auctions

The procurement of transportation services via large-scale combinatorial auctions involves a couple of complex decisions whose outcome highly influences the performance of the tender process. This paper examines the shipper's task of selecting a subset of the submitted bids which efficiently trades off total procurement cost against expected carrier performance. To solve this bi-objective winner determination problem, we propose a Pareto-based greedy randomized adaptive search procedure (GRASP). As a post-optimizer we use a path relinking procedure which is hybridized with branch-and-bound. Several variants of this algorithm are evaluated by means of artificial test instances which comply with important real-world characteristics. The two best variants prove superior to a previously published Pareto-based evolutionary algorithm.

Intermodal exchange stations in the city of Madrid

The City of Madrid is putting into operation Intermodal Exchange Stations (IESs) to make connections between urban and suburban transportation modes easier for users of public transportation. The purpose of this article is to evaluate the actual effects that the implementation of IESs in the City of Madrid has on the affected stakeholders: users, public transportation operators, infrastructure managers, the government, the abutters and other citizens. We develop a methodology intended to help assess the welfare gains and losses for each stakeholder. Then we apply this methodology to the case study of the Avenida de América IES in the city of Madrid. We found that it is indeed possible to arrive at win–win solutions for the funding of urban transportation infrastructure, as long as the cost-benefit ratio of the project is high enough. Commuters save travel time. Bus companies diminish their costs of operation. The abutters gain in quality of life. The private operator of the infrastructure makes a fair profit. And the government is able to promote these infrastructure facilities without spending more of its scarce budgetary resources.