4 Presentations

• 
  10:30 AM - 11:00 AM

  Heuristics for Blood Distribution: Case Study in Thailand

  • Pornpimol Chaiwuttisak, presenter, University of Southampton
  • Honora Smith, Mathematics and Management, University of Southampton
  • Yue Wu, Management, University of Southampton

  Regional Blood Centres (RBCs) have been established to collect blood from donors, prepare various blood products, test donated blood to ensure that blood without hepatitis, syphilis, and HIV and distribute safe blood to provincial hospitals. Currently, hospitals must collect blood using their own vehicles. As a consequence, it is difficult to manage logistics costs efficiently and control a quality standard of blood during transportation. In addition, hospitals' blood orders often exceed actual demands because supply is limited. As a result, amounts of blood supplied are reduced so that the supply to all hospitals is equitable. Planning regular schedules and routes is proposed to alleviate this situation. This research studies routes for blood services to hospitals in the Upper North region of Thailand, as a case study in a developing country. It forms part of a wider study of the supply chain process to fulfill hospital demands for fresh, quality blood supplies. An important consideration is transportation costs which have an effect on the total system costs in the network. The main objectives are to arrange a schedule for a one-week planning horizon and routes for blood delivery from the RBCs or the distribution centres to hospitals. We investigate two policies for blood distribution: single visit frequency and multiple visit frequency for different hospitals.

  For the first policy with one visit frequency for all hospitals, hospitals are clustered by geographical data into six groups for delivery on six days per week. Because the problem is NP-hard, heuristics and meta-heuristic methods are used to handle the large data set for this case study problem. Both Clarke and Wright (C&W) Single and Parallel Saving algorithms are compared as the solution methods to minimize the total distances. Then, local search is applied to improve the initial solutions. These are further compared with solutions obtained from the Greedy Randomized Adaptive Search Procedures (GRASP). It is found that GRASP can give a better solution than C&W on all clusters. The maximum number of vehicles needed for blood distribution with the same visit frequency is two. As a second policy, we assign differing frequencies of delivery to hospitals, according to hospital size and distance from the Regional Blood Centre. A fixed blood supply is assumed in this case. The problem thus contains the elements of schedule planning and routing, as in periodic vehicle routing problem. The availability of blood supply is based on historical data. Hospitals that are close together are allocated to the same route in each day. Each hospital receives blood by the proportion of its blood usage to the total blood supply subject to meeting the required visit frequency. This policy requires a greater total distance travelled than the first policy, but it can meet customer satisfaction in an improved manner.

• 
  11:00 AM - 11:30 AM

  Vehicle Scheduling with Respect to Vehicle-Specific Tasks

  • Jozsef Bekesi, University of Szeged
  • Balazs David, presenter, University of Szeged
  • Miklos Kresz, University of Szeged

  One of the most important problems in the optimization of public transportation is vehicle scheduling, which uses the vehicles of the company to execute timetabled trips. These vehicles are classified into depots according to their certain features (e.g. vehicle types, start locations). Solving the above problem with minimal cost leads to the multiple depot vehicle scheduling problem (MDVSP), where the components of the cost function include the daily cost of the vehicles, and distance-proportional costs for every covered trip and deadhead trip. Although the MDVSP is NP-hard [3], several different models and algorithms were published in literature that can be applied effectively in practice. An overview of these methods can be found in [4].
  However, the solutions given by the MDVSP cannot be considered complete from a practical point of view. This model considers vehicles belonging to the same depot uniform both in costs and in properties, while the actual vehicles assigned to the schedules are more important from a practical point of view. Moreover, the solutions of the MDVSP do not take into account the so called vehicle-specific tasks like refueling, maintenance or parking.
  To our knowledge, only a few papers from literature address the above vehicle-specific needs [2,5]. There are two main approaches to deal with the problem. Solving it sequentially is a heuristic method, where we solve an MDVSP first, then transform them to satisfy vehicles-specific tasks. Such an algorithm can be seen in [1]. Te other (combined) approach is to consider the needs of the vehicles together with the vehicle scheduling problem.
  Our presentation introduces the above combined approach. We create a set-partitioning model for the problem, where every subset corresponds to a vehicle, and the elements of these subsets are the feasible events of that vehicle. The model is solved using a column generation method. The efficiency of the algorithm is presented on real-life and random generated instances as well, and the results are compared to that of the sequential method in [1].

  [1] Balogh, J., Békési, J., Galambos, G., and Krész, M., Model and Algorithm for a Vehicle Scheduling Problem with Refueling, In: Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems, 229−231, 2009.
  [2] Banihashemi, M., Haghani, A. Optimization Model for Large-Scale Bus Transit Scheduling Problems, Transportation Research Record, 1733, 23-30, 2000.
  [3] Bertossi, A.A., Carraresi, P., and Gallo, G., On Some Matching Problems Arising in Vehicle Scheduling Models, Networks, 17, 271–281, 1987.
  [4] Bunte, S. and Kliewer, N., An overview on vehicle scheduling models, Journal of Public Transport, 1(4), 299–317, 2009.
  [5] Wang, H., Shen, J. Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints., Applied Mathematics and Computation 190, 1237—1249, 2007.

• 
  11:30 AM - 12:00 PM

  A Metaheuristic for the Multi-zone Multi-trip Vehicle Routing Problem with Time Windows

  • Phuong Nguyen Khanh, presenter, Université de Montréal
  • Teodor Gabriel Crainic, Université du Québec à Montréal
  • Michel Toulouse, Oklahoma State University

  The Multi-zone Multi-trip Vehicle Routing Problem with Time Windows (MZT-VRPTW), a problem arising from the second tier of the two-tiered city logistic system, is an extension of the VRPTW involving both designing and assigning routes to vehicles within the time synchronization restrictions. In the MZT-VRPTW setting, a homogeneous fleet of vehicles operates out of a single garage to deliver customer-specific loads, available at particular facilities during particular operating time intervals. Vehicles must synchronize their arrivals at facilities with the respective operating time periods, that is, time windows at facilities are hard and vehicles are not permitted to arrive in advance and wait. Particular waiting stations may be used by the vehicles to wait for the next appointment. A vehicle route thus leaves the garage to visit a first facility within its operating time periods and load freight, proceeds to deliver it to customers within their hard time windows, and then moves to its next appointment to a facility, possibly stopping to wait for the appropriate time at a waiting station. The route continues until either there are no more loads to deliver or its cost becomes noncompetitive compared to other routes. The vehicle returns to the garage in both cases. The objective is to minimize the total cost, which is made up of the fixed cost of using vehicles and the routing costs of servicing customers and moving between facilities. We propose a tabu search meta-heuristic for the MZT-VRPTW. Two types of neighborhoods, corresponding to the two sets of decisions of the problem, together with a strategy controlling the selection of the neighborhood type for particular phases of the search, provide the means to set up and combine exploration and exploitation capabilities for the search. A diversification strategy, guided by an elite solution set and a frequency-based memory, is also used to drive the search to potentially unexplored good regions and, hopefully, enhance the solution quality. Extensive numerical experiments and comparisons with the literature show that the proposed tabu search yields very high quality solutions, improving those currently published.

  Keywords: Vehicle routing, time windows, multi-zone, multi-trip, synchronization, tabu search, multiple neighborhoods.

• 
  12:00 PM - 12:30 PM

  Pickup and Delivery Problem with the Choice of Multiple Cross-Docks

  • Mohammad Yousef Maknoon, presenter, Polytechnique Montréal
  • Gilbert Laporte, HEC Montréal

  In pickup and delivery problem with the possibility of cross-docking, a homogenous set of vehicles carry freights from origins to destinations. Each request has a time frame and it could either, be picked up and delivered by multiple vehicles via cross-docks, or be transferred by the same vehicle. The objective is to propose efficient routes via which all requests are served within time limitations while reducing total transportation cost. The cost is evaluated based on time spent, material handling process and travelling distance. Previously, this problem has been investigated for the case where only a single cross-dock exists to consolidate the freights. However, in reality, there is more than one cross-dock which complicates the process of routing and consolidations. We employ an adaptive large neighborhood search to solve the problem in a reasonable time. This approach is also used to evaluate possible scenarios on transshipment requests.