A hybrid genetic algorithm for the multi-depot vehicle routing problem

The distribution of finished products from depots to customers is a practical and challenging problem in logistics management. Better routing and scheduling decisions can result in higher level of customer satisfaction because more customers can be served in a shorter time. The distribution problem is generally formulated as the vehicle routing problem (VRP). Nevertheless, there is a rigid assumption that there is only one depot. In cases, for instance, where a logistics company has more than one depot, the VRP is not suitable. To resolve this limitation, this paper focuses on the VRP with multiple depots, or multi-depot VRP (MDVRP). The MDVRP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To deal with the problem efficiently, two hybrid genetic algorithms (HGAs) are developed in this paper. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method and the nearest neighbor heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different problem sizes. It is proved that the performance of HGA2 is superior to that of HGA1 in terms of the total delivery time.

A new three phase method (SDP method) for the multi-objective vehicle routing problem with simultaneous delvery and pickup (VRPSDP)

Transportation service operators are witnessing a growing demand for bi-directional movement of goods. Given this, the following thesis considers an extension to the vehicle routing problem (VRP) known as the delivery and pickup transportation problem (DPP), where delivery and pickup demands may occupy the same route. The problem is formulated here as the vehicle routing problem with simultaneous delivery and pickup (VRPSDP), which requires the concurrent service of the demands at the customer location. This formulation provides the greatest opportunity for cost savings for both the service provider and recipient. The aims of this research are to propose a new theoretical design to solve the multi-objective VRPSDP, provide software support for the suggested design and validate the method through a set of experiments. A new real-life based multi-objective VRPSDP is studied here, which requires the minimisation of the often conflicting objectives: operated vehicle fleet size, total routing distance and the maximum variation between route distances (workload variation). The former two objectives are commonly encountered in the domain and the latter is introduced here because it is essential for real-life routing problems. The VRPSDP is defined as a hard combinatorial optimisation problem, therefore an approximation method, Simultaneous Delivery and Pickup method (SDPmethod) is proposed to solve it. The SDPmethod consists of three phases. The first phase constructs a set of diverse partial solutions, where one is expected to form part of the near-optimal solution. The second phase determines assignment possibilities for each sub-problem. The third phase solves the sub-problems using a parallel genetic algorithm. The suggested genetic algorithm is improved by the introduction of a set of tools: genetic operator switching mechanism via diversity thresholds, accuracy analysis tool and a new fitness evaluation mechanism. This three phase method is proposed to address the shortcoming that exists in the domain, where an initial solution is built only then to be completely dismantled and redesigned in the optimisation phase. In addition, a new routing heuristic, RouteAlg, is proposed to solve the VRPSDP sub-problem, the travelling salesman problem with simultaneous delivery and pickup (TSPSDP). The experimental studies are conducted using the well known benchmark Salhi and Nagy (1999) test problems, where the SDPmethod and RouteAlg solutions are compared with the prominent works in the VRPSDP domain. The SDPmethod has demonstrated to be an effective method for solving the multi-objective VRPSDP and the RouteAlg for the TSPSDP.

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.

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.

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.

Throughput-based rate adaptation algorithm for IEEE 802.11 vehicle networks

A key problem with IEEE 802.11 technology is adaptation of the transmission rates to the changing channel conditions, which is more challenging in vehicular networks. Although rate adaptation problem has been extensively studied for static residential and enterprise network scenarios, there is little work dedicated to the IEEE 802.11 rate adaptation in vehicular networks. Here, the authors are motivated to study the IEEE 802.11 rate adaptation problem in infrastructure-based vehicular networks. First of all, the performances of several existing rate adaptation algorithms under vehicle network scenarios, which have been widely used for static network scenarios, are evaluated. Then, a new rate adaptation algorithm is proposed to improve the network performance. In the new rate adaptation algorithm, the technique of sampling candidate transmission modes is used, and the effective throughput associated with a transmission mode is the metric used to choose among the possible transmission modes. The proposed algorithm is compared to several existing rate adaptation algorithms by simulations, which shows significant performance improvement under various system and channel configurations. An ideal signal-to-noise ratio (SNR)-based rate adaptation algorithm in which accurate channel SNR is assumed to be always available is also implemented for benchmark performance comparison.

Eco-car : a perfect vehicle for technical design teaching?

Design methods and tools are generally best learned and developed experientially [1]. Finding appropriate vehicles for delivering these to students is becoming increasingly challenging, especially when considering only those that will enthuse, intrigue and inspire. This paper traces the development of different eco-car design and build projects which competed in the Shell Eco-Marathon. The cars provided opportunities for experiential learning through a formal learning cycle of CDIO (Conceive, Design, Implement, Operate) or the more traditional understand, explore, create, validate, with both teams developing a functional finished prototype. Lessons learned were applied through the design of a third and fourth eco-car using experimental techniques with bio-composites, combining the knowledge of fibre reinforced composite materials and adhesives with the plywood construction techniques of the two teams. The paper discusses the importance of applying materials and techniques to a real world problem. It will also explore how eco-car and comparing traditional materials and construction techniques with high tech composite materials is an ideal teaching, learning and assessment vehicle for technical design techniques.