Algoritmi di ottimizzazione per il bus touring problem.

Nel campo della Ricerca Operativa e dei problemi di ottimizzazione viene presentato un problema, denominato Bus Touring Problem (BTP), che modella una problematica riguardante il carico e l’instradamento di veicoli nella presenza di di vincoli temporali e topologici sui percorsi. Nel BTP, ci si pone il problema di stabilire una serie di rotte per la visita di punti di interesse dislocati geograficamente da parte di un insieme di comitive turistiche, ciascuna delle quali stabilisce preferenze riguardo le visite. Per gli spostamenti sono disponibili un numero limitato di mezzi di trasporto, in generale eterogenei, e di capacitá limitata. Le visite devono essere effettuate rispettando finestre temporali che indicano i periodi di apertura dei punti di interesse; per questi, inoltre, é specificato un numero massimo di visite ammesse. L’obiettivo é di organizzare il carico dei mezzi di trasporto e le rotte intraprese in modo da massimizzare la soddisfazione complessiva dei gruppi di turisti nel rispetto dei vincoli imposti. Viene presentato un algoritmo euristico basato su Tabu Search appositamente ideato e progettato per la risoluzione del BTP. Vengono presentati gli esperimenti effettuati riguardo la messa appunto dei parametri dell'algoritmo su un insieme di problemi di benchmark. Vengono presentati risultati estesi riguardo le soluzioni dei problemi. Infine, vengono presentate considerazioni ed indicazioni di sviluppo futuro in materia.

Special reports on trip and vehicle attributes: based on data from 1990 Nationwide Personal Transportation Survey (NPTS).

Federal Highway Administration, Washington, D.C.

Nested Rollout Policy Adaptation for optimizing vehicle selection in complex VRPs

The goal of Vehicle Routing Problems (VRP) and their variations is to transport a set of orders with the minimum number of vehicles at least cost. Most approaches are designed to solve specific problem variations independently, whereas in real world applications, different constraints are handled concurrently. This research extends solutions obtained for the traveling salesman problem with time windows to a much wider class of route planning problems in logistics. The work describes a novel approach that:  supports a heterogeneous fleet of vehicles  dynamically reduces the number of vehicles  respects individual capacity restrictions  satisfies pickup and delivery constraints  takes Hamiltonian paths (rather than cycles) The proposed approach uses Monte-Carlo Tree Search and in particular Nested Rollout Policy Adaptation. For the evaluation of the work, real data from the industry was obtained and tested and the results are reported.

Rural and remote road safety study : final report

• Introduction: Concern and action for rural road safety is relatively new in Australia in comparison to the field of traffic safety as a whole. In 2003, a program of research was begun by the Centre for Accident Research and Road Safety - Queensland (CARRS-Q) and the Rural Health Research Unit (RHRU) at James Cook University to investigate factors contributing to serious rural road crashes in the North Queensland region. This project was funded by the Premier’s Department, Main Roads Department, Queensland Transport, QFleet, Queensland Rail, Queensland Ambulance Service, Department of Natural Resources and Queensland Police Service. Additional funding was provided by NRMA Insurance for a PhD scholarship. In-kind support was provided through the four hospitals used for data collection, namely Cairns Base Hospital, The Townsville Hospital, Mount Isa Hospital and Atherton Hospital.----- The primary aim of the project was to: Identify human factors related to the occurrence of serious traffic incidents in rural and remote areas of Australia, and to the trauma suffered by persons as a result of these incidents, using a sample drawn from a rural and remote area in North Queensland.----- The data and analyses presented in this report are the core findings from two broad studies: a general examination of fatalities and casualties from rural and remote crashes for the period 1 March 2004 until 30 June 2007, and a further linked case-comparison study of hospitalised patients compared with a sample of non-crash-involved drivers.----- • Method: The study was undertaken in rural North Queensland, as defined by the Australian Bureau of Statistics (ABS) statistical divisions of North Queensland, Far North Queensland and North-West Queensland. Urban areas surrounding Townsville, Thuringowa and Cairns were not included. The study methodology was centred on serious crashes, as defined by a resulting hospitalisation for 24 hours or more and/or a fatality. Crashes meeting this criteria within the North Queensland region between 1 March 2004 and 30 June 2007 were identified through hospital records and interviewed where possible. Additional data was sourced from coroner’s reports, the Queensland Transport road crash database, the Queensland Ambulance Service and the study hospitals in the region.----- This report is divided into chapters corresponding to analyses conducted on the collected crash and casualty data.----- Chapter 3 presents an overview of all crashes and casualties identified during the study period. Details are presented in regard to the demographics and road user types of casualties; the locations, times, types, and circumstances of crashes; along with the contributing circumstances of crashes.----- Chapter 4 presents the results of summary statistics for all casualties for which an interview was able to be conducted. Statistics are presented separately for drivers and riders, passengers, pedestrians and cyclists. Details are also presented separately for drivers and riders crashing in off-road and on-road settings. Results from questionnaire data are presented in relation to demographics; the experience of the crash in narrative form; vehicle characteristics and maintenance; trip characteristics (e.g. purpose and length of journey; periods of fatigue and monotony; distractions from driving task); driving history; alcohol and drug use; medical history; driving attitudes, intentions and behaviour; attitudes to enforcement; and experience of road safety advertising.----- Chapter 5 compares the above-listed questionnaire results between on-road crash-involved casualties and interviews conducted in the region with non-crash-involved persons. Direct comparisons as well as age and sex adjusted comparisons are presented.----- Chapter 6 presents information on those casualties who were admitted to one of the study hospitals during the study period. Brief information is given regarding the demographic characteristics of these casualties. Emergency services’ data is used to highlight the characteristics of patient retrieval and transport to and between hospitals. The major injuries resulting from the crashes are presented for each region of the body and analysed by vehicle type, occupant type, seatbelt status, helmet status, alcohol involvement and nature of crash. Estimates are provided of the costs associated with in-hospital treatment and retrieval.----- Chapter 7 describes the characteristics of the fatal casualties and the nature and circumstances of the crashes. Demographics, road user types, licence status, crash type and contributing factors for crashes are presented. Coronial data is provided in regard to contributing circumstances (including alcohol, drugs and medical conditions), cause of death, resulting injuries, and restraint and helmet use.----- Chapter 8 presents the results of a comparison between casualties’ crash descriptions and police-attributed crash circumstances. The relative frequency of contributing circumstances are compared both broadly within the categories of behavioural, environmental, vehicle related, medical and other groupings and specifically for circumstances within these groups.----- Chapter 9 reports on the associated research projects which have been undertaken on specific topics related to rural road safety.----- Finally, Chapter 10 reports on the conclusions and recommendations made from the program of research.---- • Major Recommendations : From the findings of these analyses, a number of major recommendations were made: + Male drivers and riders - Male drivers and riders should continue to be the focus of interventions, given their very high representation among rural and remote road crash fatalities and serious injuries.----- - The group of males aged between 30 and 50 years comprised the largest number of casualties and must also be targeted for change if there is to be a meaningful improvement in rural and remote road safety.----- + Motorcyclists - Single vehicle motorcycle crashes constitute over 80% of serious, on-road rural motorcycle crashes and need particular attention in development of policy and infrastructure.----- - The motorcycle safety consultation process currently being undertaken by Queensland Transport (via the "Motorbike Safety in Queensland - Consultation Paper") is strongly endorsed. As part of this process, particular attention needs to be given to initiatives designed to reduce rural and single vehicle motorcycle crashes.----- - The safety of off-road riders is a serious problem that falls outside the direct responsibility of either Transport or Health departments. Responsibility for this issue needs to be attributed to develop appropriate policy, regulations and countermeasures.----- + Road safety for Indigenous people - Continued resourcing and expansion of The Queensland Aboriginal Peoples and Torres Strait Islander Peoples Driver Licensing Program to meet the needs of remote and Indigenous communities with significantly lower licence ownership levels.----- - Increased attention needs to focus on the contribution of geographic disadvantage (remoteness) factors to remote and Indigenous road trauma.----- + Road environment - Speed is the ‘final common pathway’ in determining the severity of rural and remote crashes and rural speed limits should be reduced to 90km/hr for sealed off-highway roads and 80km/hr for all unsealed roads as recommended in the Austroads review and in line with the current Tasmanian government trial.----- - The Department of Main Roads should monitor rural crash clusters and where appropriate work with local authorities to conduct relevant audits and take mitigating action. - The international experts at the workshop reviewed the data and identified the need to focus particular attention on road design management for dangerous curves. They also indicated the need to maximise the use of audio-tactile linemarking (audible lines) and rumble strips to alert drivers to dangerous conditions and behaviours.----- + Trauma costs - In accordance with Queensland Health priorities, recognition should be given to the substantial financial costs associated with acute management of trauma resulting from serious rural and remote crashes.----- - Efforts should be made to develop a comprehensive, regionally specific costing formula for road trauma that incorporates the pre-hospital, hospital and post-hospital phases of care. This would inform health resource allocation and facilitate the evaluation of interventions.----- - The commitment of funds to the development of preventive strategies to reduce rural and remote crashes should take into account the potential cost savings associated with trauma.----- - A dedicated study of the rehabilitation needs and associated personal and healthcare costs arising from rural and remote road crashes should be undertaken.----- + Emergency services - While the study has demonstrated considerable efficiency in the response and retrieval systems of rural and remote North Queensland, relevant Intelligent Transport Systems technologies (such as vehicle alarm systems) to improve crash notification should be both developed and evaluated.----- + Enforcement - Alcohol and speed enforcement programs should target the period between 2 and 6pm because of the high numbers of crashes in the afternoon period throughout the rural region.----- + Drink driving - Courtesy buses should be advocated and schemes such as the Skipper project promoted as local drink driving countermeasures in line with the very high levels of community support for these measures identified in the hospital study.------ - Programs should be developed to target the high levels of alcohol consumption identified in rural and remote areas and related involvement in crashes.----- - Referrals to drink driving rehabilitation programs should be mandated for recidivist offenders.----- + Data requirements - Rural and remote road crashes should receive the same quality of attention as urban crashes. As such, it is strongly recommended that increased resources be committed to enable dedicated Forensic Crash Units to investigate rural and remote fatal and serious injury crashes.----- - Transport department records of rural and remote crashes should record the crash location using the national ARIA area classifications used by health departments as a means to better identifying rural crashes.----- - Rural and remote crashes tend to be unnoticed except in relatively infrequent rural reviews. They should receive the same level of attention and this could be achieved if fatalities and fatal crashes were coded by the ARIA classification system and included in regular crash reporting.----- - Health, Transport and Police agencies should collect a common, minimal set of data relating to road crashes and injuries, including presentations to small rural and remote health facilities.----- + Media and community education programmes - Interventions seeking to highlight the human contribution to crashes should be prioritised. Driver distraction, alcohol and inappropriate speed for the road conditions are key examples of such behaviours.----- - Promotion of basic safety behaviours such as the use of seatbelts and helmets should be given a renewed focus.----- - Knowledge, attitude and behavioural factors that have been identified for the hospital Brief Intervention Trial should be considered in developing safety campaigns for rural and remote people. For example challenging the myth of the dangerous ‘other’ or ‘non-local’ driver.----- - Special educational initiatives on the issues involved in rural and remote driving should be undertaken. For example the material used by Main Roads, the Australian Defence Force and local initiatives.

Cooperative multi-AUV tracking of phytoplankton blooms based on ocean model predictions

In recent years, ocean scientists have started to employ many new forms of technology as integral pieces in oceanographic data collection for the study and prediction of complex and dynamic ocean phenomena. One area of technological advancement in ocean sampling if the use of Autonomous Underwater Vehicles (AUVs) as mobile sensor plat- forms. Currently, most AUV deployments execute a lawnmower- type pattern or repeated transects for surveys and sampling missions. An advantage of these missions is that the regularity of the trajectory design generally makes it easier to extract the exact path of the vehicle via post-processing. However, if the deployment region for the pattern is poorly selected, the AUV can entirely miss collecting data during an event of specific interest. Here, we consider an innovative technology toolchain to assist in determining the deployment location and executed paths for AUVs to maximize scientific information gain about dynamically evolving ocean phenomena. In particular, we provide an assessment of computed paths based on ocean model predictions designed to put AUVs in the right place at the right time to gather data related to the understanding of algal and phytoplankton blooms.

2 Algorithms For 3-Layer Channel Routing

A channel router is an important design aid in the design automation of VLSI circuit layout. Many algorithms have been developed based on various wiring models with routing done on two layers. With the recent advances in VLSI process technology, it is possible to have three independent layers for interconnection. In this paper two algorithms are presented for three-layer channel routing. The first assumes a very simple wiring model. This enables the routing problem to be solved optimally in a time of O(n log n). The second algorithm is for a different wiring model and has an upper bound of O(n2) for its execution time. It uses fewer horizontal tracks than the first algorithm. For the second model the channel width is not bounded by the channel density.

Neural network based optimal routing algorithm for communication networks

This paper presents the capability of the neural networks as a computational tool for solving constrained optimization problem, arising in routing algorithms for the present day communication networks. The application of neural networks in the optimum routing problem, in case of packet switched computer networks, where the goal is to minimize the average delays in the communication have been addressed. The effectiveness of neural network is shown by the results of simulation of a neural design to solve the shortest path problem. Simulation model of neural network is shown to be utilized in an optimum routing algorithm known as flow deviation algorithm. It is also shown that the model will enable the routing algorithm to be implemented in real time and also to be adaptive to changes in link costs and network topology. (C) 2002 Elsevier Science Ltd. All rights reserved.

MPI-based parallel synchronous vector evaluated particle swarm optimization for multi-objective design optimization of composite structures

This paper presents a decentralized/peer-to-peer architecture-based parallel version of the vector evaluated particle swarm optimization (VEPSO) algorithm for multi-objective design optimization of laminated composite plates using message passing interface (MPI). The design optimization of laminated composite plates being a combinatorially explosive constrained non-linear optimization problem (CNOP), with many design variables and a vast solution space, warrants the use of non-parametric and heuristic optimization algorithms like PSO. Optimization requires minimizing both the weight and cost of these composite plates, simultaneously, which renders the problem multi-objective. Hence VEPSO, a multi-objective variant of the PSO algorithm, is used. Despite the use of such a heuristic, the application problem, being computationally intensive, suffers from long execution times due to sequential computation. Hence, a parallel version of the PSO algorithm for the problem has been developed to run on several nodes of an IBM P720 cluster. The proposed parallel algorithm, using MPI's collective communication directives, establishes a peer-to-peer relationship between the constituent parallel processes, deviating from the more common master-slave approach, in achieving reduction of computation time by factor of up to 10. Finally we show the effectiveness of the proposed parallel algorithm by comparing it with a serial implementation of VEPSO and a parallel implementation of the vector evaluated genetic algorithm (VEGA) for the same design problem. (c) 2012 Elsevier Ltd. All rights reserved.

Time-dependent Hyperstar algorithm for robust vehicle navigation in time-dependent stochastic road networks.

The vehicle navigation problem studied in Bell (2009) is revisited and a time-dependent reverse Hyperstar algorithm is presented. This minimises the expected time of arrival at the destination, and all intermediate nodes, where expectation is based on a pessimistic (or risk-averse) view of unknown link delays. This may also be regarded as a hyperpath version of the Chabini and Lan (2002) algorithm, which itself is a time-dependent A* algorithm. Links are assigned undelayed travel times and maximum delays, both of which are potentially functions of the time of arrival at the respective link. The driver seeks probabilities for link use that minimise his/her maximum exposure to delay on the approach to each node, leading to the determination of the pessimistic expected time of arrival. Since the context considered is vehicle navigation where the driver is not making repeated trips, the probability of link use may be interpreted as a measure of link attractiveness, so a link with a zero probability of use is unattractive while a link with a probability of use equal to one will have no attractive alternatives. A solution algorithm is presented and proven to solve the problem provided the node potentials are feasible and a FIFO condition applies for undelayed link travel times. The paper concludes with a numerical example.

Evaluation of a Load Profiling Approach to Routing Guaranteed Bandwidth Flows

To support the diverse Quality of Service (QoS) requirements of real-time (e.g. audio/video) applications in integrated services networks, several routing algorithms that allow for the reservation of the needed bandwidth over a Virtual Circuit (VC) established on one of several candidate routes have been proposed. Traditionally, such routing is done using the least-loaded concept, and thus results in balancing the load across the set of candidate routes. In a recent study, we have established the inadequacy of this load balancing practice and proposed the use of load profiling as an alternative. Load profiling techniques allow the distribution of "available" bandwidth across a set of candidate routes to match the characteristics of incoming VC QoS requests. In this paper we thoroughly characterize the performance of VC routing using load profiling and contrast it to routing using load balancing and load packing. We do so both analytically and via extensive simulations of multi-class traffic routing in Virtual Path (VP) based networks. Our findings confirm that for routing guaranteed bandwidth flows in VP networks, load balancing is not desirable as it results in VP bandwidth fragmentation, which adversely affects the likelihood of accepting new VC requests. This fragmentation is more pronounced when the granularity of VC requests is large. Typically, this occurs when a common VC is established to carry the aggregate traffic flow of many high-bandwidth real-time sources. For VP-based networks, our simulation results show that our load-profiling VC routing scheme performs better or as well as the traditional load-balancing VC routing in terms of revenue under both skewed and uniform workloads. Furthermore, load-profiling routing improves routing fairness by proactively increasing the chances of admitting high-bandwidth connections.

A nested location-routing heuristic using route length estimation

A nested heuristic approach that uses route length approximation is proposed to solve the location-routing problem. A new estimation formula for route length approximation is also developed. The heuristic is evaluated empirically against the sequential method and a recently developed nested method for location routing problems. This testing is carried out on a set of problems of 400 customers and around 15 to 25 depots with good results.

Polyhedral study of mixed integer sets arising from inventory problems

“Branch-and-cut” algorithm is one of the most efficient exact approaches to solve mixed integer programs. This algorithm combines the advantages of a pure branch-and-bound approach and cutting planes scheme. Branch-and-cut algorithm computes the linear programming relaxation of the problem at each node of the search tree which is improved by the use of cuts, i.e. by the inclusion of valid inequalities. It should be taken into account that selection of strongest cuts is crucial for their effective use in branch-and-cut algorithm. In this thesis, we focus on the derivation and use of cutting planes to solve general mixed integer problems, and in particular inventory problems combined with other problems such as distribution, supplier selection, vehicle routing, etc. In order to achieve this goal, we first consider substructures (relaxations) of such problems which are obtained by the coherent loss of information. The polyhedral structure of those simpler mixed integer sets is studied to derive strong valid inequalities. Finally those strong inequalities are included in the cutting plane algorithms to solve the general mixed integer problems. We study three mixed integer sets in this dissertation. The first two mixed integer sets arise as a subproblem of the lot-sizing with supplier selection, the network design and the vendor-managed inventory routing problems. These sets are variants of the well-known single node fixed-charge network set where a binary or integer variable is associated with the node. The third set occurs as a subproblem of mixed integer sets where incompatibility between binary variables is considered. We generate families of valid inequalities for those sets, identify classes of facet-defining inequalities, and discuss the separation problems associated with the inequalities. Then cutting plane frameworks are implemented to solve some mixed integer programs. Preliminary computational experiments are presented in this direction.

Graphical constraints: a graphical user interface for constraint problems

A constraint satisfaction problem is a classical artificial intelligence paradigm characterized by a set of variables (each variable with an associated domain of possible values), and a set of constraints that specify relations among subsets of these variables. Solutions are assignments of values to all variables that satisfy all the constraints. Many real world problems may be modelled by means of constraints. The range of problems that can use this representation is very diverse and embraces areas like resource allocation, scheduling, timetabling or vehicle routing. Constraint programming is a form of declarative programming in the sense that instead of specifying a sequence of steps to execute, it relies on properties of the solutions to be found, which are explicitly defined by constraints. The idea of constraint programming is to solve problems by stating constraints which must be satisfied by the solutions. Constraint programming is based on specialized constraint solvers that take advantage of constraints to search for solutions. The success and popularity of complex problem solving tools can be greatly enhanced by the availability of friendly user interfaces. User interfaces cover two fundamental areas: receiving information from the user and communicating it to the system; and getting information from the system and deliver it to the user. Despite its potential impact, adequate user interfaces are uncommon in constraint programming in general. The main goal of this project is to develop a graphical user interface that allows to, intuitively, represent constraint satisfaction problems. The idea is to visually represent the variables of the problem, their domains and the problem constraints and enable the user to interact with an adequate constraint solver to process the constraints and compute the solutions. Moreover, the graphical interface should be capable of configure the solver’s parameters and present solutions in an appealing interactive way. As a proof of concept, the developed application – GraphicalConstraints – focus on continuous constraint programming, which deals with real valued variables and numerical constraints (equations and inequalities). RealPaver, a state-of-the-art solver in continuous domains, was used in the application. The graphical interface supports all stages of constraint processing, from the design of the constraint network to the presentation of the end feasible space solutions as 2D or 3D boxes.

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

Desenvolvimento de um modelo computacional para a ampliação do atendimento do Programa de Acessibilidade Especial Porta a Porta - PRAE

Worldwide, the demand for transportation services for persons with disabilities, the elderly, and persons with reduced mobility have increased in recent years. The population is aging, governments need to adapt to this reality, and this fact could mean business opportunities for companies. Within this context is inserted the Programa de Acessibilidade Especial porta a porta PRAE, a door to door public transportation service from the city of Natal-RN in Brazil. The research presented in this dissertation seeks to develop a programming model which can assist the process of decision making of managers of the shuttle. To that end, it was created an algorithm based on methods of generating approximate solutions known as heuristics. The purpose of the model is to increase the number of people served by the PRAE, given the available fleet, generating optimized schedules routes. The PRAE is a problem of vehicle routing and scheduling of dial-a-ride - DARP, the most complex type among the routing problems. The validation of the method of resolution was made by comparing the results derived by the model and the currently programming method. It is expected that the model is able to increase the current capacity of the service requests of transport