Loading…
A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints
We consider a vehicle routing problem which seeks to minimize cost subject to time window and synchronization constraints. In this problem, the fleet of vehicles is categorized into regular and special vehicles. Some customers require both vehicles’ services, whose service start times at the custome...
Saved in:
Published in: | Computers & operations research 2020-12, Vol.124, p.105085, Article 105085 |
---|---|
Main Authors: | , , , , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
cited_by | cdi_FETCH-LOGICAL-c357t-b85a86807ea18149cbd9a4cac74953618fb4eceb815ec2b122c43fde784954613 |
---|---|
cites | cdi_FETCH-LOGICAL-c357t-b85a86807ea18149cbd9a4cac74953618fb4eceb815ec2b122c43fde784954613 |
container_end_page | |
container_issue | |
container_start_page | 105085 |
container_title | Computers & operations research |
container_volume | 124 |
creator | Hà, Minh Hoàng Nguyen, Tat Dat Nguyen Duy, Thinh Pham, Hoang Giang Do, Thuy Rousseau, Louis-Martin |
description | We consider a vehicle routing problem which seeks to minimize cost subject to time window and synchronization constraints. In this problem, the fleet of vehicles is categorized into regular and special vehicles. Some customers require both vehicles’ services, whose service start times at the customer are synchronized. Despite its important real-world application, this problem has rarely been studied in the literature. To solve the problem, we propose a Constraint Programming (CP) model and an Adaptive Large Neighborhood Search (ALNS) in which the design of insertion operators is based on solving linear programming (LP) models to check the insertion feasibility. A number of acceleration techniques is also proposed to significantly reduce the computational time. The computational experiments show that our new CP model finds better solutions than an existing CP-based ALNS, when used on small instances with 25 customers and with a much shorter running time. Our LP-based ALNS dominates the CP-based ALNS, in terms of solution quality, when it provides solutions with better objective values, on average, for all instance classes. This demonstrates the advantage of using linear programming instead of constraint programming when dealing with a variant of vehicle routing problems with relatively tight constraints, which is often considered to be more favorable for CP-based methods. We also adapt our algorithm to solve a well-studied variant of the problem, and the obtained results show that the algorithm provides good solutions as state-of-the-art approaches and improves four best known solutions. |
doi_str_mv | 10.1016/j.cor.2020.105085 |
format | article |
fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2505722003</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0305054820302021</els_id><sourcerecordid>2505722003</sourcerecordid><originalsourceid>FETCH-LOGICAL-c357t-b85a86807ea18149cbd9a4cac74953618fb4eceb815ec2b122c43fde784954613</originalsourceid><addsrcrecordid>eNp9UctOwzAQjBBIlMIHcLPEOcV24sYVp6riJVXiAmfLcTaNq8Qua7cV_A__iaty6Im97K5mZ3akybJbRieMsun9emI8Tjjlh11QKc6yES2oyKko5fnJfJldhbCmqSrORtnPnDjYE-NdiKiti2SDfoV6GKxbkcE30BPtGqJJbx1oPIXzWgdIUKM30e6A9BpXkOTsqqs9dt43JCSK6UjrkcQOyA46a3og6LfxoJ_E6h4GsrexI-HLmQ69s986Wu9OPIXr7KLVfYCbvz7OPp4e3xcv-fLt-XUxX-amEFXMaym0nEpagWaSlTNTNzNdGm2qciaKKZNtXYKBWjIBhteMc1MWbQOVTHg5ZcU4uzvqJmOfWwhRrf0WXXqpuKCi4pzSIl2x45VBHwJCqzZoB41filF1SEOtVUpDHdJQxzQS5-HIgWR_ZwFVMBacgcYimKgab_9h_wIfFZbM</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2505722003</pqid></control><display><type>article</type><title>A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints</title><source>ScienceDirect Journals</source><creator>Hà, Minh Hoàng ; Nguyen, Tat Dat ; Nguyen Duy, Thinh ; Pham, Hoang Giang ; Do, Thuy ; Rousseau, Louis-Martin</creator><creatorcontrib>Hà, Minh Hoàng ; Nguyen, Tat Dat ; Nguyen Duy, Thinh ; Pham, Hoang Giang ; Do, Thuy ; Rousseau, Louis-Martin</creatorcontrib><description>We consider a vehicle routing problem which seeks to minimize cost subject to time window and synchronization constraints. In this problem, the fleet of vehicles is categorized into regular and special vehicles. Some customers require both vehicles’ services, whose service start times at the customer are synchronized. Despite its important real-world application, this problem has rarely been studied in the literature. To solve the problem, we propose a Constraint Programming (CP) model and an Adaptive Large Neighborhood Search (ALNS) in which the design of insertion operators is based on solving linear programming (LP) models to check the insertion feasibility. A number of acceleration techniques is also proposed to significantly reduce the computational time. The computational experiments show that our new CP model finds better solutions than an existing CP-based ALNS, when used on small instances with 25 customers and with a much shorter running time. Our LP-based ALNS dominates the CP-based ALNS, in terms of solution quality, when it provides solutions with better objective values, on average, for all instance classes. This demonstrates the advantage of using linear programming instead of constraint programming when dealing with a variant of vehicle routing problems with relatively tight constraints, which is often considered to be more favorable for CP-based methods. We also adapt our algorithm to solve a well-studied variant of the problem, and the obtained results show that the algorithm provides good solutions as state-of-the-art approaches and improves four best known solutions.</description><identifier>ISSN: 0305-0548</identifier><identifier>EISSN: 0305-0548</identifier><identifier>DOI: 10.1016/j.cor.2020.105085</identifier><language>eng</language><publisher>New York: Elsevier Ltd</publisher><subject>Adaptive large neighborhood search ; Algorithms ; Computing time ; Constraint modelling ; Constraint programming ; Customer services ; Customers ; Insertion ; Linear programming ; Operations research ; Route planning ; Run time (computers) ; Synchronism ; Synchronization constraint ; Time synchronization ; Time window ; Vehicle routing ; Vehicle routing problem ; Vehicles ; Windows (intervals)</subject><ispartof>Computers & operations research, 2020-12, Vol.124, p.105085, Article 105085</ispartof><rights>2020</rights><rights>Copyright Pergamon Press Inc. Dec 2020</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c357t-b85a86807ea18149cbd9a4cac74953618fb4eceb815ec2b122c43fde784954613</citedby><cites>FETCH-LOGICAL-c357t-b85a86807ea18149cbd9a4cac74953618fb4eceb815ec2b122c43fde784954613</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Hà, Minh Hoàng</creatorcontrib><creatorcontrib>Nguyen, Tat Dat</creatorcontrib><creatorcontrib>Nguyen Duy, Thinh</creatorcontrib><creatorcontrib>Pham, Hoang Giang</creatorcontrib><creatorcontrib>Do, Thuy</creatorcontrib><creatorcontrib>Rousseau, Louis-Martin</creatorcontrib><title>A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints</title><title>Computers & operations research</title><description>We consider a vehicle routing problem which seeks to minimize cost subject to time window and synchronization constraints. In this problem, the fleet of vehicles is categorized into regular and special vehicles. Some customers require both vehicles’ services, whose service start times at the customer are synchronized. Despite its important real-world application, this problem has rarely been studied in the literature. To solve the problem, we propose a Constraint Programming (CP) model and an Adaptive Large Neighborhood Search (ALNS) in which the design of insertion operators is based on solving linear programming (LP) models to check the insertion feasibility. A number of acceleration techniques is also proposed to significantly reduce the computational time. The computational experiments show that our new CP model finds better solutions than an existing CP-based ALNS, when used on small instances with 25 customers and with a much shorter running time. Our LP-based ALNS dominates the CP-based ALNS, in terms of solution quality, when it provides solutions with better objective values, on average, for all instance classes. This demonstrates the advantage of using linear programming instead of constraint programming when dealing with a variant of vehicle routing problems with relatively tight constraints, which is often considered to be more favorable for CP-based methods. We also adapt our algorithm to solve a well-studied variant of the problem, and the obtained results show that the algorithm provides good solutions as state-of-the-art approaches and improves four best known solutions.</description><subject>Adaptive large neighborhood search</subject><subject>Algorithms</subject><subject>Computing time</subject><subject>Constraint modelling</subject><subject>Constraint programming</subject><subject>Customer services</subject><subject>Customers</subject><subject>Insertion</subject><subject>Linear programming</subject><subject>Operations research</subject><subject>Route planning</subject><subject>Run time (computers)</subject><subject>Synchronism</subject><subject>Synchronization constraint</subject><subject>Time synchronization</subject><subject>Time window</subject><subject>Vehicle routing</subject><subject>Vehicle routing problem</subject><subject>Vehicles</subject><subject>Windows (intervals)</subject><issn>0305-0548</issn><issn>0305-0548</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><recordid>eNp9UctOwzAQjBBIlMIHcLPEOcV24sYVp6riJVXiAmfLcTaNq8Qua7cV_A__iaty6Im97K5mZ3akybJbRieMsun9emI8Tjjlh11QKc6yES2oyKko5fnJfJldhbCmqSrORtnPnDjYE-NdiKiti2SDfoV6GKxbkcE30BPtGqJJbx1oPIXzWgdIUKM30e6A9BpXkOTsqqs9dt43JCSK6UjrkcQOyA46a3og6LfxoJ_E6h4GsrexI-HLmQ69s986Wu9OPIXr7KLVfYCbvz7OPp4e3xcv-fLt-XUxX-amEFXMaym0nEpagWaSlTNTNzNdGm2qciaKKZNtXYKBWjIBhteMc1MWbQOVTHg5ZcU4uzvqJmOfWwhRrf0WXXqpuKCi4pzSIl2x45VBHwJCqzZoB41filF1SEOtVUpDHdJQxzQS5-HIgWR_ZwFVMBacgcYimKgab_9h_wIfFZbM</recordid><startdate>20201201</startdate><enddate>20201201</enddate><creator>Hà, Minh Hoàng</creator><creator>Nguyen, Tat Dat</creator><creator>Nguyen Duy, Thinh</creator><creator>Pham, Hoang Giang</creator><creator>Do, Thuy</creator><creator>Rousseau, Louis-Martin</creator><general>Elsevier Ltd</general><general>Pergamon Press Inc</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20201201</creationdate><title>A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints</title><author>Hà, Minh Hoàng ; Nguyen, Tat Dat ; Nguyen Duy, Thinh ; Pham, Hoang Giang ; Do, Thuy ; Rousseau, Louis-Martin</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c357t-b85a86807ea18149cbd9a4cac74953618fb4eceb815ec2b122c43fde784954613</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Adaptive large neighborhood search</topic><topic>Algorithms</topic><topic>Computing time</topic><topic>Constraint modelling</topic><topic>Constraint programming</topic><topic>Customer services</topic><topic>Customers</topic><topic>Insertion</topic><topic>Linear programming</topic><topic>Operations research</topic><topic>Route planning</topic><topic>Run time (computers)</topic><topic>Synchronism</topic><topic>Synchronization constraint</topic><topic>Time synchronization</topic><topic>Time window</topic><topic>Vehicle routing</topic><topic>Vehicle routing problem</topic><topic>Vehicles</topic><topic>Windows (intervals)</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hà, Minh Hoàng</creatorcontrib><creatorcontrib>Nguyen, Tat Dat</creatorcontrib><creatorcontrib>Nguyen Duy, Thinh</creatorcontrib><creatorcontrib>Pham, Hoang Giang</creatorcontrib><creatorcontrib>Do, Thuy</creatorcontrib><creatorcontrib>Rousseau, Louis-Martin</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Computers & operations research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hà, Minh Hoàng</au><au>Nguyen, Tat Dat</au><au>Nguyen Duy, Thinh</au><au>Pham, Hoang Giang</au><au>Do, Thuy</au><au>Rousseau, Louis-Martin</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints</atitle><jtitle>Computers & operations research</jtitle><date>2020-12-01</date><risdate>2020</risdate><volume>124</volume><spage>105085</spage><pages>105085-</pages><artnum>105085</artnum><issn>0305-0548</issn><eissn>0305-0548</eissn><abstract>We consider a vehicle routing problem which seeks to minimize cost subject to time window and synchronization constraints. In this problem, the fleet of vehicles is categorized into regular and special vehicles. Some customers require both vehicles’ services, whose service start times at the customer are synchronized. Despite its important real-world application, this problem has rarely been studied in the literature. To solve the problem, we propose a Constraint Programming (CP) model and an Adaptive Large Neighborhood Search (ALNS) in which the design of insertion operators is based on solving linear programming (LP) models to check the insertion feasibility. A number of acceleration techniques is also proposed to significantly reduce the computational time. The computational experiments show that our new CP model finds better solutions than an existing CP-based ALNS, when used on small instances with 25 customers and with a much shorter running time. Our LP-based ALNS dominates the CP-based ALNS, in terms of solution quality, when it provides solutions with better objective values, on average, for all instance classes. This demonstrates the advantage of using linear programming instead of constraint programming when dealing with a variant of vehicle routing problems with relatively tight constraints, which is often considered to be more favorable for CP-based methods. We also adapt our algorithm to solve a well-studied variant of the problem, and the obtained results show that the algorithm provides good solutions as state-of-the-art approaches and improves four best known solutions.</abstract><cop>New York</cop><pub>Elsevier Ltd</pub><doi>10.1016/j.cor.2020.105085</doi></addata></record> |
fulltext | fulltext |
identifier | ISSN: 0305-0548 |
ispartof | Computers & operations research, 2020-12, Vol.124, p.105085, Article 105085 |
issn | 0305-0548 0305-0548 |
language | eng |
recordid | cdi_proquest_journals_2505722003 |
source | ScienceDirect Journals |
subjects | Adaptive large neighborhood search Algorithms Computing time Constraint modelling Constraint programming Customer services Customers Insertion Linear programming Operations research Route planning Run time (computers) Synchronism Synchronization constraint Time synchronization Time window Vehicle routing Vehicle routing problem Vehicles Windows (intervals) |
title | A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints |
url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-24T12%3A58%3A17IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20new%20constraint%20programming%20model%20and%20a%20linear%20programming-based%20adaptive%20large%20neighborhood%20search%20for%20the%20vehicle%20routing%20problem%20with%20synchronization%20constraints&rft.jtitle=Computers%20&%20operations%20research&rft.au=H%C3%A0,%20Minh%20Ho%C3%A0ng&rft.date=2020-12-01&rft.volume=124&rft.spage=105085&rft.pages=105085-&rft.artnum=105085&rft.issn=0305-0548&rft.eissn=0305-0548&rft_id=info:doi/10.1016/j.cor.2020.105085&rft_dat=%3Cproquest_cross%3E2505722003%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c357t-b85a86807ea18149cbd9a4cac74953618fb4eceb815ec2b122c43fde784954613%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2505722003&rft_id=info:pmid/&rfr_iscdi=true |