CoBrand-IORA_H-web-1
Search
Close this search box.

Exact approaches for the pickup and delivery problem with loading cost

Li Xue, School of Management, Xi׳an Jiaotong University, No. 28, Xianning West Road, Xi׳an, Shaanxi 710049, PR China. Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Hong Kong. International Center of Management Science and Engineering, School of Management and Engineering, Nanjing University, Nanjing 210093, PR China

Zhixing Luo, International Center of Management Science and Engineering, School of Management and Engineering, Nanjing University, Nanjing 210093, PR China

Andrew Lim, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore. International Center of Management Science and Engineering, School of Management and Engineering, Nanjing University, Nanjing 210093, PR China. Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Hong Kong

Download
ABSTRACT

In this paper, we propose a branch-and-cut algorithm and a branch-and-price algorithm to solve the pickup and delivery problem with loading cost (PDPLC), which is a new problem derived from the classic pickup and delivery problem (PDP) by considering the loading cost in the objective function. Applications of the PDPLC arise in healthcare transportation where the objective function is customer-centric or service-based. In the branch-and-price algorithm, we devise an ad hoc label-setting algorithm to solve the pricing problem and employ the bounded bidirectional search strategy to accelerate the label-setting algorithm. The proposed algorithms were tested on a set of instances generated by a common data generator in the literature. The computational results showed that the branch-and-price algorithm outperformed the branch-and-cut algorithm by a large margin, and can solve instances with 40 requests to optimality in a reasonable time frame.

The Institute of Operations Research and Analytics (IORA) is a part of NUS’s Smart Nation Research Cluster.

Innovation 4.0, 3 Research Link, #04-01, Singapore 117602

IORA

Resources