I have few questions, where and how the data (such as destination address and location of the package hold by seller) is stored? Surely it's not public blockchain which can be seen anyone, right?
It need to be stored in a decentralized way. Why not bitcoin? You can just hash it with your private key I guess. The problem is how much does it cost to store few strings of data on blockchain. For example
this
IALbjlgCEo75teC4/CPG761/mhAG0u5QK5DkA7VHuorgdfu06DQQvESCXwWT0HtShYP+253R8OlXl7NBu84RdL4=
is the signature for the coordinates of New York using a TestNet4 address.
You don't use private key to perform hashing. I think you're talking about either digital signature or encryption. But my point is not many people willingly to share their building address.
The problem is how much does it cost to store few strings of data on blockchain.
Yeah, it's not cheap if you intend to use Bitcoin blockchain. In addition, it could become very expensive when many people create Bitcoin TX which increase fee rate suggestion.
If the market is decentralized how can I store this data on a central server? I can't. I must create a new blockchain to start this market or can I use bitcoin?
Nobody can stop from using Bitcoin blockchain, although you'll receive some critic. Although you have option to use one of Bitcoin sidechain or L2.