A tutorial on the use of graph coloring for some problems in robotics

We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the location of the Entry/Exit station where the ro...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2009, Vol.192 (1), p.41-55
Main Authors: Demange, Marc, Ekim, Tınaz, de Werra, Dominique
Format: Article
Language:English
Subjects:
AGV
Automated storage system
Generalized vertex coloring
Graph coloring
l-modal sequence
Materials handling
Optimization
Pallet loading problem
Permutation graphs
Pick up robots
Pick up robots AGV Automated storage system Pallet loading problem l-modal sequence Generalized vertex coloring Permutation graphs
Robotics
Studies
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-c447t-a954332dced2e13741d0dec6e27f247d6e662c6d9c931b78e71eefb6d697dc2a3
cites cdi_FETCH-LOGICAL-c447t-a954332dced2e13741d0dec6e27f247d6e662c6d9c931b78e71eefb6d697dc2a3
container_end_page 55
container_issue 1
container_start_page 41
container_title European journal of operational research
container_volume 192
creator Demange, Marc
Ekim, Tınaz
de Werra, Dominique
description We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the location of the Entry/Exit station where the robot unloads the collected items after each trip along the corridor. The links of these systems with generalized coloring problems and other applications such that train shunting and pallet loading problems are discussed and related results are obtained. We conclude with several open questions on the topic.
doi_str_mv 10.1016/j.ejor.2007.09.018
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_204148392</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0377221707009423</els_id><sourcerecordid>1557681511</sourcerecordid><originalsourceid>FETCH-LOGICAL-c447t-a954332dced2e13741d0dec6e27f247d6e662c6d9c931b78e71eefb6d697dc2a3</originalsourceid><addsrcrecordid>eNp9UNFKwzAUDaLgnP6AT8H31iRtkwZ8GWPqYOCLPocuud1StqYm3WB_7x0THw2c3JCcc-7NIeSRs5wzLp-7HLoQc8GYypnOGa-vyITXSmSyluyaTFihVCYEV7fkLqWOMcYrXk3IYkbHwxiib3Y09HTcAj0koKGlm9gMW2rDDh_7DW1DpCnsgQ4xrHewT9T3FI9h9Dbdk5u22SV4-K1T8vW6-Jy_Z6uPt-V8tspsWaoxa3RVFoVwFpwAXqiSO-bAShCqFaVyEqQUVjptdcHXqgbFAdq1dFIrZ0VTTMnTxReH-D5AGk0XDrHHlkawkpd1oQWSxIVkY0gpQmuG6PdNPBnOzDkt05lzWuaclmHaYFooWl5EEQawfwrAhVRI5miKhmuB-wmBUo3Fny8RA6LkpqrMdtyj18vFCzCKo4dokvXQ4699BDsaF_x_o_wAfGWMBw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>204148392</pqid></control><display><type>article</type><title>A tutorial on the use of graph coloring for some problems in robotics</title><source>ScienceDirect Freedom Collection 2022-2024</source><creator>Demange, Marc ; Ekim, Tınaz ; de Werra, Dominique</creator><creatorcontrib>Demange, Marc ; Ekim, Tınaz ; de Werra, Dominique</creatorcontrib><description>We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the location of the Entry/Exit station where the robot unloads the collected items after each trip along the corridor. The links of these systems with generalized coloring problems and other applications such that train shunting and pallet loading problems are discussed and related results are obtained. We conclude with several open questions on the topic.</description><identifier>ISSN: 0377-2217</identifier><identifier>EISSN: 1872-6860</identifier><identifier>DOI: 10.1016/j.ejor.2007.09.018</identifier><identifier>CODEN: EJORDT</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>AGV ; Automated storage system ; Generalized vertex coloring ; Graph coloring ; l-modal sequence ; Materials handling ; Optimization ; Pallet loading problem ; Permutation graphs ; Pick up robots ; Pick up robots AGV Automated storage system Pallet loading problem l-modal sequence Generalized vertex coloring Permutation graphs ; Robotics ; Studies</subject><ispartof>European journal of operational research, 2009, Vol.192 (1), p.41-55</ispartof><rights>2007 Elsevier B.V.</rights><rights>Copyright Elsevier Sequoia S.A. Jan 1, 2009</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c447t-a954332dced2e13741d0dec6e27f247d6e662c6d9c931b78e71eefb6d697dc2a3</citedby><cites>FETCH-LOGICAL-c447t-a954332dced2e13741d0dec6e27f247d6e662c6d9c931b78e71eefb6d697dc2a3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,4023,27922,27923,27924</link.rule.ids><backlink>$$Uhttp://econpapers.repec.org/article/eeeejores/v_3a192_3ay_3a2009_3ai_3a1_3ap_3a41-55.htm$$DView record in RePEc$$Hfree_for_read</backlink></links><search><creatorcontrib>Demange, Marc</creatorcontrib><creatorcontrib>Ekim, Tınaz</creatorcontrib><creatorcontrib>de Werra, Dominique</creatorcontrib><title>A tutorial on the use of graph coloring for some problems in robotics</title><title>European journal of operational research</title><description>We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the location of the Entry/Exit station where the robot unloads the collected items after each trip along the corridor. The links of these systems with generalized coloring problems and other applications such that train shunting and pallet loading problems are discussed and related results are obtained. We conclude with several open questions on the topic.</description><subject>AGV</subject><subject>Automated storage system</subject><subject>Generalized vertex coloring</subject><subject>Graph coloring</subject><subject>l-modal sequence</subject><subject>Materials handling</subject><subject>Optimization</subject><subject>Pallet loading problem</subject><subject>Permutation graphs</subject><subject>Pick up robots</subject><subject>Pick up robots AGV Automated storage system Pallet loading problem l-modal sequence Generalized vertex coloring Permutation graphs</subject><subject>Robotics</subject><subject>Studies</subject><issn>0377-2217</issn><issn>1872-6860</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2009</creationdate><recordtype>article</recordtype><recordid>eNp9UNFKwzAUDaLgnP6AT8H31iRtkwZ8GWPqYOCLPocuud1StqYm3WB_7x0THw2c3JCcc-7NIeSRs5wzLp-7HLoQc8GYypnOGa-vyITXSmSyluyaTFihVCYEV7fkLqWOMcYrXk3IYkbHwxiib3Y09HTcAj0koKGlm9gMW2rDDh_7DW1DpCnsgQ4xrHewT9T3FI9h9Dbdk5u22SV4-K1T8vW6-Jy_Z6uPt-V8tspsWaoxa3RVFoVwFpwAXqiSO-bAShCqFaVyEqQUVjptdcHXqgbFAdq1dFIrZ0VTTMnTxReH-D5AGk0XDrHHlkawkpd1oQWSxIVkY0gpQmuG6PdNPBnOzDkt05lzWuaclmHaYFooWl5EEQawfwrAhVRI5miKhmuB-wmBUo3Fny8RA6LkpqrMdtyj18vFCzCKo4dokvXQ4699BDsaF_x_o_wAfGWMBw</recordid><startdate>2009</startdate><enddate>2009</enddate><creator>Demange, Marc</creator><creator>Ekim, Tınaz</creator><creator>de Werra, Dominique</creator><general>Elsevier B.V</general><general>Elsevier</general><general>Elsevier Sequoia S.A</general><scope>DKI</scope><scope>X2L</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7TB</scope><scope>8FD</scope><scope>FR3</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>2009</creationdate><title>A tutorial on the use of graph coloring for some problems in robotics</title><author>Demange, Marc ; Ekim, Tınaz ; de Werra, Dominique</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c447t-a954332dced2e13741d0dec6e27f247d6e662c6d9c931b78e71eefb6d697dc2a3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2009</creationdate><topic>AGV</topic><topic>Automated storage system</topic><topic>Generalized vertex coloring</topic><topic>Graph coloring</topic><topic>l-modal sequence</topic><topic>Materials handling</topic><topic>Optimization</topic><topic>Pallet loading problem</topic><topic>Permutation graphs</topic><topic>Pick up robots</topic><topic>Pick up robots AGV Automated storage system Pallet loading problem l-modal sequence Generalized vertex coloring Permutation graphs</topic><topic>Robotics</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Demange, Marc</creatorcontrib><creatorcontrib>Ekim, Tınaz</creatorcontrib><creatorcontrib>de Werra, Dominique</creatorcontrib><collection>RePEc IDEAS</collection><collection>RePEc</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>Engineering 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>European journal of operational research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Demange, Marc</au><au>Ekim, Tınaz</au><au>de Werra, Dominique</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A tutorial on the use of graph coloring for some problems in robotics</atitle><jtitle>European journal of operational research</jtitle><date>2009</date><risdate>2009</risdate><volume>192</volume><issue>1</issue><spage>41</spage><epage>55</epage><pages>41-55</pages><issn>0377-2217</issn><eissn>1872-6860</eissn><coden>EJORDT</coden><abstract>We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the location of the Entry/Exit station where the robot unloads the collected items after each trip along the corridor. The links of these systems with generalized coloring problems and other applications such that train shunting and pallet loading problems are discussed and related results are obtained. We conclude with several open questions on the topic.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/j.ejor.2007.09.018</doi><tpages>15</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0377-2217
ispartof European journal of operational research, 2009, Vol.192 (1), p.41-55
issn 0377-2217
1872-6860
language eng
recordid cdi_proquest_journals_204148392
source ScienceDirect Freedom Collection 2022-2024
subjects AGV
Automated storage system
Generalized vertex coloring
Graph coloring
l-modal sequence
Materials handling
Optimization
Pallet loading problem
Permutation graphs
Pick up robots
Pick up robots AGV Automated storage system Pallet loading problem l-modal sequence Generalized vertex coloring Permutation graphs
Robotics
Studies
title A tutorial on the use of graph coloring for some problems in robotics
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-09T07%3A57%3A03IST&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%20tutorial%20on%20the%20use%20of%20graph%20coloring%20for%20some%20problems%20in%20robotics&rft.jtitle=European%20journal%20of%20operational%20research&rft.au=Demange,%20Marc&rft.date=2009&rft.volume=192&rft.issue=1&rft.spage=41&rft.epage=55&rft.pages=41-55&rft.issn=0377-2217&rft.eissn=1872-6860&rft.coden=EJORDT&rft_id=info:doi/10.1016/j.ejor.2007.09.018&rft_dat=%3Cproquest_cross%3E1557681511%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c447t-a954332dced2e13741d0dec6e27f247d6e662c6d9c931b78e71eefb6d697dc2a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=204148392&rft_id=info:pmid/&rfr_iscdi=true