The Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs

Battarra, Maria; Erdoğan, Güneş; Laporte, Gilbert; Vigo, Daniele
August 2010
Transportation Science;Aug2010, Vol. 44 Issue 3, p383
Academic Journal
This paper introduces a new variant of the one-to-many-to-one single vehicle pickup and delivery problems (SVPDP) that incorporates the handling cost incurred when rearranging the load at the customer locations. The simultaneous optimization of routing and handling costs is difficult, and the resulting loading patterns are hard to implement in practice. However, this option makes economical sense in contexts where the routing cost dominates the handling cost. We have proposed some simplified policies applicable to such contexts. The first is a two-phase heuristic in which the tour having minimum routing cost is initially determined by optimally solving an SVPDP, and the optimal handling policy is then determined for that tour. In addition, branch-and-cut algorithms based on integer linear programming formulations are proposed, in which routing and handling decisions are simultaneously optimized, but the handling decisions are restricted to three simplified policies. The formulations are strengthened by means of problem specific valid inequalities. The proposed methods have been extensively tested on instances involving up to 25 customers and hundreds of items. Our results show the impact of the handling aspect on the customer sequencing and indicate that the simplified handling policies favorably compare with the optimal one.


Related Articles

  • Dynamic capacitated lot-sizing problems: a classification and review of solution approaches. Buschk�hl, Lisbeth; Sahling, Florian; Helber, Stefan; Tempelmeier, Horst // OR Spectrum;Apr2010, Vol. 32 Issue 2, p231 

    This paper presents a review of four decades of research on dynamic lot-sizing with capacity constraints. We discuss both different modeling approaches to the optimization problems and different algorithmic solution approaches. The focus is on research that separates the lot-sizing problem from...

  • Multicriteria, multi-user scheduling in grids with advance reservation. Kurowski, Krzysztof; Oleksiak, Ariel; Weglarz, Jan // Journal of Scheduling;Oct2010, Vol. 13 Issue 5, p493 

    In this paper, we propose a new method for multi-user, multicriteria job scheduling in Grid environments with QoS guarantees concerning time and cost. The main goal of our method is to find a fair schedule of jobs that were submitted by multiple users. To obtain a schedule which is satisfactory...

  • On-line hierarchical job scheduling on grids with admissible allocation. Tchernykh, Andrei; Schwiegelshohn, Uwe; Yahyapour, Ramin; Kuzjurin, Nikolai // Journal of Scheduling;Oct2010, Vol. 13 Issue 5, p545 

    In this paper, we address non-preemptive online scheduling of parallel jobs on a Grid. Our Grid consists of a large number of identical processors that are divided into several machines. We consider a Grid scheduling model with two stages. At the first stage, jobs are allocated to a suitable...

  • Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines. Dereniowski, Dariusz; Kubiak, Wieslaw // Journal of Scheduling;Oct2010, Vol. 13 Issue 5, p479 

    The paper addresses the problem of multi-slot just-in-time scheduling. Unlike the existing literature on this subject, it studies a more general criterion�the minimization of the schedule makespan rather than the minimization of the number of slots used by schedule. It gives an O( nlog ...

  • MPM Job-shop under Availability Constraints. Zribi, Nozha; Duta, Luminita // International Journal of Computers, Communications & Control;Dec2009, Vol. 4 Issue 4, p439 

    A large part of scheduling literature assumes that machines are available all the time. In this paper, the MPM Job-shop scheduling problem, where the machine maintenance has to be performed within certain time intervals inducing machine unavailability, is studied. Two approaches to solve the...


    In this paper, a new schedule generation scheme for resource-constrained project scheduling problems is proposed. Given a project scheduling problem and a priority rule, a schedule generation scheme determines a single feasible solution by inserting one by one each activity, according to their...

  • A Dynamic Rescheduling Model with Multi-Agent System and Its Solution Method. Fuqing Zhao; Jizhe Wang; Junbiao Wang; Jonrinaldi, Jonrinaldi // Strojniski Vestnik / Journal of Mechanical Engineering;Feb2012, Vol. 58 Issue 2, p81 

    Dynamic rescheduling problem is an important issue in modern manufacturing system with the feature of combinatorial computation complexity. A dynamic rescheduling model, which is based on Multi-Agent System (MAS), was proposed. The communication and negotiation mechanism between agents were...

  • Impact of Fair Share and its Configurations on Parallel Job Scheduling Algorithms. Vasupongayya, Sangsuree // World Academy of Science, Engineering & Technology;Oct2009, Issue 34, p102 

    To provide a better understanding of fair share policies supported by current production schedulers and their impact on scheduling performance, A relative fair share policy supported in four well-known production job schedulers is evaluated in this study. The experimental results show that fair...

  • GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times. Rodriguez, F.; Blum, C.; García-Martínez, C.; Lozano, M. // Annals of Operations Research;Dec2012, Vol. 201 Issue 1, p383 

    In this work, we tackle the problem of scheduling a set of jobs on a set of non-identical parallel machines with the goal of minimising the total weighted completion times. GRASP is a multi-start method that consists of two phases: a solution construction phase, which randomly constructs a...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics