Optimization of cable cycles : a trade-off between reliability and cost

This paper elaborates the routing of cable cycle through available routes in a building in order to link a set of devices, in a most reasonable way. Despite of the similarities to other NP-hard routing problems, the only goal is not only to minimize the cost (length of the cycle) but also to increase the reliability of the path (in case of a cable cut) which is assessed by a risk factor. Since there is often a trade-off between the risk and length factors, a criterion for ranking candidates and deciding the most reasonable solution is defined. A set of techniques is proposed to perform an efficient and exact search among candidates. A novel graph is introduced to reduce the search-space, and navigate the search toward feasible and desirable solutions. Moreover, admissible heuristic length estimation helps to early detection of partial cycles which lead to unreasonable solutions. The results show that the method provides solutions which are both technically and financially reasonable. Furthermore, it is proved that the proposed techniques are very efficient in reducing the computational time of the search to a reasonable amount.

Um algoritmo híbrido para o problema de roteamento de veículos com frotas heterogêneas

This paper aims to propose a hybrid meta-heuristics for the Heterogeneous Fleet Vehicle Routing Problem (HVRP), which is a combinatorial optimization problem NP-hard, and is characterized by the use of a limited fleet consists of different vehicles with different capacities. The hybrid method developed makes use of a memetic algorithm associated with the component optimizer Vocabulary Building. The resulting hybrid meta-heuristic was implemented in the programming language C + + and computational experiments generated good results in relation to meta-heuristic applied in isolation, proving the efficiency of the proposed method.

Metaheurísticas evolutivas para o problema de roteamento de unidades móveis de pistoneio

This paper presents metaheuristic strategies based on the framework of evolutionary algorithms (Genetic and Memetic) with the addition of Technical Vocabulary Building for solving the Problem of Optimizing the Use of Multiple Mobile Units Recovery of Oil (MRO units). Because it is an NP-hard problem, a mathematical model is formulated for the problem, allowing the construction of test instances that are used to validate the evolutionary metaheuristics developed

Análise do uso de SIG no roteamento dos veículos de coleta de resíduos sólidos domiciliares

Relata-se neste trabalho, a análise do uso de um Sistema de Informação Geográfica - SIG como ferramenta para roteirização de veículos de coleta de resíduos sólidos domiciliares. O software utilizado foi o TransCAD, versão 3.2, que permite desenvolver rotas utilizando algoritmos que incluem o procedimento de roteirização em arco. O objetivo é minimizar a extensão total a ser percorrida pelos veículos coletores. O estudo de caso foi realizado na cidade de Ilha Solteira - SP. Os dados coletados e os resultados obtidos pelo TransCAD foram processados no software Microsoft Excel. Os resultados obtidos demonstraram reduções percentuais de até 41% na distância total percorrida e de 68% no tempo total de percurso em relação ao serviço atual.

Um estudo algorítmico da programação da intervenção de sondas de produção

This work approaches the Scheduling Workover Rigs Problem (SWRP) to maintain the wells of an oil field, although difficult to resolve, is extremely important economical, technical and environmental. A mathematical formulation of this problem is presented, where an algorithmic approach was developed. The problem can be considered to find the best scheduling service to the wells by the workover rigs, taking into account the minimization of the composition related to the costs of the workover rigs and the total loss of oil suffered by the wells. This problem is similar to the Vehicle Routing Problem (VRP), which is classified as belonging to the NP-hard class. The goal of this research is to develop an algorithmic approach to solve the SWRP, using the fundamentals of metaheuristics like Memetic Algorithm and GRASP. Instances are generated for the tests to analyze the computational performance of the approaches mentioned above, using data that are close to reality. Thereafter, is performed a comparison of performance and quality of the results obtained by each one of techniques used

Progettazione e sviluppo di software di supporto alla logistica dei trasporti.

Uno dei problemi più diffusi, nell'ambito della logistica, è rappresentato dai costi di trasporto. La gestione dei flussi merci, l'approvvigionamento dei clienti, e la relativa pianifcazione della movimentazione dei veicoli, hanno incidenze notevoli sui costi di gestione aziendali, i quali vengono stimati mediamente nel 45% dei costi logistici. A ragione di questo, sono sempre di più le aziende che ricorrono all'impiego di uffici dedicati alla pianifcazione delle consegne e la gestione dei trasporti in generale. Sebbene le voci di bilancio relative al trasporto raggiungano cifre rilevanti, fno al 4% del fatturato annuo, il tema della pianifcazione viene spesso sottovalutato. Infatti la soluzione a problemi di pianifcazione e monitoraggio dei costi, è spesso demandata a procedure manuali senza supporto informatico. Nasce da qui l'esigenza di proporre uno strumento informatico che supporti gli addetti preposti alla pianifcazione, sviluppando un sistema che copra esigenze di pianifcazione dei viaggi, controllo e consuntivazione dei costi di trasporto, e monitoraggio dei mezzi in tempo reale. La proposta di Gesp srl, Geographic Information Systems, azienda italiana che opera da anni nel campo delle applicazioni software geo-spaziali, prende il nome di Nuovo Sistema Trasporti, o più semplicemente, NST. In quest'ambito prende corpo questa tesi, la quale si pone l'obiettivo di illustrare le fasi di nascita, analisi, progettazione e sviluppo di un software generico per il supporto alla logistica. Saranno così analizzati: le problematiche affrontate nella fase di defnizione, e kick-off (avvio), del progetto, il problema del routing, o Vehicle Routing Problem e le tecniche di Ricerca Operativa che vengono applicate per la sua risoluzione; le moderne metodologie di gestione e sviluppo di un software; l'architettura e le tecnologie impiegate per la distribuzione dell'applicativo.

Optimização de rotas na recolha de leite

O presente relatório tem por objectivo apresentar e descrever de forma detalhada o projecto “Optimização de rotas na recolha de leite”. Este projecto foi conduzido no âmbito do estágio curricular, realizado na parte não-lectiva do Mestrado em Sistemas de Informação de Gestão, do Instituto Superior de Contabilidade e Administração de Coimbra, tendo decorrido na empresa Lacticoop entre 03 de Outubro de 2011 e 27 de Julho de 2012. O projecto surge da necessidade da empresa optimizar as suas rotas de recolha de leite. Essa optimização pode ser subdividida em duas partes distintas: i) a recolha de dados, características e processos relativos à empresa e aos sistemas com que labora; ii) e o desenvolvimento do software necessário para a optimização de uma componente desses sistemas, associada ao processo de recolha de leite. O primeiro ponto envolve a recolha de informação sobre a política interna da empresa, a recolha de dados acerca dos veículos, rotas, consumos e condutores, assim como o levantamento de procedimentos e tecnologias utilizadas. O segundo ponto envolve a modelação do problema em estudo, o levantamento das necessidades de software para implementar o sistema de informação, a avaliação de soluções de software e desenvolvimento/adaptação da aplicação informática, assim como a implementação do software desenvolvido / adaptado e testes. Actualmente a empresa não dispõe de qualquer automatismo para a definição de rotas, sendo o processo de escalonamento de rotas feito manualmente. Este processo é bastante moroso e complexo, envolvendo a troca de informações entre o gestor e os condutores das viaturas. É um processo gradual, numa sequência de detecção de erros e correcção desses mesmos erros. Esta metodologia conduz a soluções bastante ineficientes, desde logo pela desactualização das soluções relativamente à efemeridade dos dados, especialmente ao nível de quantidades de recolha do produto. A razão da escolha de um sistema informático que permita optimizar as rotas prende-se essencialmente com a rapidez na obtenção de soluções e na capacidade de integração de dados actualizados. Este processo recorre a técnicas e modelos de optimização que envolvem o problema de Rotas de Veículos (Vehicle Routing Problem), sendo, em geral, um problema de difícil resolução em função do número de clientes envolvidos. Todavia, trata-se de um sistema que traz enormes benefícios no apoio ao processo de decisão por parte do gestor. Neste estágio pretendeu-se, como objectivo principal, desenvolver uma aplicação que permita optimizar as rotas dos veículos envolvidos no processo de recolha de leite. Os benefícios do sistema na diminuição de distâncias percorridas pelas viaturas de recolha e no aumento da eficiência do sistema de transportes, serão evidenciados no trabalho desenvolvido. A aplicação foi criada no software Eclipse (utilizando a linguagem Java). Na primeira fase do projecto estava previsto monitorizar as rotas e consumos dos veículos através da tecnologia de geo-posicionamento por satélite (GPS), de forma a atribuir comissões sobre a poupança de combustível aos condutores dos veículos. Não foi possível concluir esta fase devido à inexistência dessa tecnologia nas viaturas e pelo facto de a empresa ter retirado essa prioridade a esse investimento.

Optimization of physical distribution problem in logistics management

Physical distribution plays an imporant role in contemporary logistics management. Both satisfaction level of of customer and competitiveness of company can be enhanced if the distribution problem is solved optimally. The multi-depot vehicle routing problem (MDVRP) belongs to a practical logistics distribution problem, which consists of three critical issues: customer assignment, customer routing, and vehicle sequencing. According to the literatures, the solution approaches for the MDVRP are not satisfactory because some unrealistic assumptions were made on the first sub-problem of the MDVRP, ot the customer assignment problem. To refine the approaches, the focus of this paper is confined to this problem only. This paper formulates the customer assignment problem as a minimax-type integer linear programming model with the objective of minimizing the cycle time of the depots where setup times are explicitly considered. Since the model is proven to be MP-complete, a genetic algorithm is developed for solving the problem. The efficiency and effectiveness of the genetic algorithm are illustrated by a numerical example.

Premium e-grocery:exploring value in logistics integrated service solutions

E-grocery is gradually becoming viable or a necessity for many families. Yet, most e-supermarkets are seen as providers of low value "staple" and bulky goods mainly. While each store has a large number of SKU available, these products are mainly necessity goods with low marginal value for hedonistic consumption. A need to acquire diverse products (e.g., organic), premium priced products (e.g., wine) for special occasions (e.g., anniversary, birthday), or products just for health related reasons (e.g., allergies, diabetes) are yet to be served via one-stop e-tailers. In this paper, we design a mathematical model that takes into account consumers' geo-demographics and multi-product sourcing capacity for creating critical mass and profit. Our mathematical model is a variant of Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), which we extend by adding intermediate locations for trucks to meet and exchange goods. We illustrate our model for the city of Istanbul using GIS maps, and discuss its various extensions as well as managerial implications.

Improving “last mile” delivery performance to retailers in hub and spoke distribution systems

Purpose – The purpose of this paper is to investigate the “last mile” delivery link between a hub and spoke distribution system and its customers. The proportion of retail, as opposed to non-retail (trade) customers using this type of distribution system has been growing in the UK. The paper shows the applicability of simulation to demonstrate changes in overall delivery policy to these customers. Design/methodology/approach – A case-based research method was chosen with the aim to provide an exemplar of practice and test the proposition that simulation can be used as a tool to investigate changes in delivery policy. Findings – The results indicate the potential improvement in delivery performance, specifically in meeting timed delivery performance, that could be made by having separate retail and non-retail delivery runs from the spoke terminal to the customer. Research limitations/implications – The simulation study does not attempt to generate a vehicle routing schedule but demonstrates the effects of a change on delivery performance when comparing delivery policies. Practical implications – Scheduling and spreadsheet software are widely used and provide useful assistance in the design of delivery runs and the allocation of staff to those delivery runs. This paper demonstrates to managers the usefulness of investigating the efficacy of current design rules and presents simulation as a suitable tool for this analysis. Originality/value – A simulation model is used in a novel application to test a change in delivery policy in response to a changing delivery profile of increased retail deliveries.

The multiple pheromone ant clustering algorithm and its application to real world domains

The Multiple Pheromone Ant Clustering Algorithm (MPACA) models the collective behaviour of ants to find clusters in data and to assign objects to the most appropriate class. It is an ant colony optimisation approach that uses pheromones to mark paths linking objects that are similar and potentially members of the same cluster or class. Its novelty is in the way it uses separate pheromones for each descriptive attribute of the object rather than a single pheromone representing the whole object. Ants that encounter other ants frequently enough can combine the attribute values they are detecting, which enables the MPACA to learn influential variable interactions. This paper applies the model to real-world data from two domains. One is logistics, focusing on resource allocation rather than the more traditional vehicle-routing problem. The other is mental-health risk assessment. The task for the MPACA in each domain was to predict class membership where the classes for the logistics domain were the levels of demand on haulage company resources and the mental-health classes were levels of suicide risk. Results on these noisy real-world data were promising, demonstrating the ability of the MPACA to find patterns in the data with accuracy comparable to more traditional linear regression models. © 2013 Polish Information Processing Society.

A new VRPPD model and a hybrid heuristic solution approach for e-tailing

We analyze a business model for e-supermarkets to enable multi-product sourcing capacity through co-opetition (collaborative competition). The logistics aspect of our approach is to design and execute a network system where “premium” goods are acquired from vendors at multiple locations in the supply network and delivered to customers. Our specific goals are to: (i) investigate the role of premium product offerings in creating critical mass and profit; (ii) develop a model for the multiple-pickup single-delivery vehicle routing problem in the presence of multiple vendors; and (iii) propose a hybrid solution approach. To solve the problem introduced in this paper, we develop a hybrid metaheuristic approach that uses a Genetic Algorithm for vendor selection and allocation, and a modified savings algorithm for the capacitated VRP with multiple pickup, single delivery and time windows (CVRPMPDTW). The proposed Genetic Algorithm guides the search for optimal vendor pickup location decisions, and for each generated solution in the genetic population, a corresponding CVRPMPDTW is solved using the savings algorithm. We validate our solution approach against published VRPTW solutions and also test our algorithm with Solomon instances modified for CVRPMPDTW.

Problème de déploiement de ressources dans le cas des feux de forêts majeurs - Opérations aériennes

Chaque année le feu brûle quelques dizaines de milliers d’hectares de forêts québécoises. Le coût annuel de prévention et de lutte contre les feux de forêts au Québec est de l’ordre de plusieurs dizaines de millions de dollars. Le présent travail contribue à la réduction de ces coûts à travers l’automatisation du processus de planification des opérations de suppression des feux de forêts majeurs. Pour ce faire, un modèle mathématique linéaire en nombres entiers a été élaboré, résolu et testé; introduisant un nouveau cas particulier à la littérature des Problèmes de Tournées de Véhicules (VRP). Ce modèle mathématique concerne le déploiement aérien des ressources disponibles pour l’extinction des incendies. Le modèle élaboré a été testé avec CPLEX sur des cas tirés de données réelles. Il a permis de réduire le temps de planification des opérations d’extinction des feux de forêts majeurs de 75% dans les situations courantes.

Otimização da recolha de resíduos urbanos : caso de estudo de Aveiro

O elevado custo da operação de recolha de resíduos urbanos e a necessidade de cumprir metas dispostas em instrumentos legais são duas motivações que conduzem à necessidade de otimizar o serviço da recolha de resíduos. A otimização da recolha de resíduos é um problema de elevada complexidade de resolução que envolve a análise de redes de transporte. O presente trabalho propõe soluções de otimização da recolha de resíduos urbanos indiferenciados, a partir de um caso de estudo: o percurso RSU I 06 do município de Aveiro. Para este efeito, recorreu-se a uma aplicação informática de representação e análise geográfica: software ArcGIS denominada ArcMap e sua extensão Network Analyst, desenvolvida para calcular circuitos otimizados entre pontos de interesse. O trabalho realizado de aplicação do Network Analyst inclui a apresentação de duas das suas funcionalidades (Route e Vehicle Routing Problem). Em relação ao atual circuito de recolha e com base nos ensaios efetuados, foi possível concluir que esta aplicação permite obter circuitos de recolha otimizados mais curtos ou com menor duração. Contudo, ao nível da gestão permitiu concluir que, com a atual capacidade de contentorização, seria viável reduzir a frequência de recolha de seis vezes por semana para metade, dividindo a área de recolha em duas áreas, de acordo com as necessidades de cada local, reduzindo ainda mais o esforço de recolha. A aplicação do Network Analyst ao caso de estudo, permitiu concluir que é um software com muito interesse no processo de gestão da recolha de resíduos urbanos, apesar de apresentar algumas restrições de aplicação e que a qualidade/eficácia do procedimento de otimização depende da qualidade dos dados de entrada, em particular do descritivo geográfico disponível para os arruamentos e, em larga medida, também depende do modelo de gestão considerado.